Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 285

1. All strings formed by two different substrings


2. One substring starting with a’s followed by equal number of b’s i.e. ‘ab, aabb,.’


3. Followed by other substring that generates c’s only i.e. ‘c, cc, ccc......’
   Let S is the starting symbol and A and C are other non terminal symbols, then following
   are the productions (P)
   S → AC (corresponding to 1)
   A → a b | a A b (corresponding to 2) and
   C → c | c C (corresponding to 3)
   Thus the grammar G = ({S, A, C}, {a, b}, S, P)
   We can also see that,
   S ⇒ A C ⇒ a b C ⇒ a b c,
   a a b b c, or
   S ⇒ A C ⇒ a A b C ⇒ a a b b C
   a a b b c C → a a b b c c and so on.
   Example 11.7. Prove that Language L = {ak bl cl/k ≥ 1 and l ≥ 1} is a CFL.
   Sol. We observe that L contains strings of following nature, i.e.


4. all strings formed by two substrings,


5. first substring formed over symbol a’s viz. ‘a, aa, aaa.........’


6. followed by other substring that contains the symbol b’s followed by a equal number
   of c’s viz. ‘bc, bbcc, bbbccc.........’
   Let S is the starting symbol and A and B are the other non terminals.
   So, under above observations the following are the productions (P)
   S → A B (corresponds to 1)
   A → a | a A (corresponds to 2) and
   B → b c | b B c (corresponds to 3)
   These productions fulfill the restrictions that all are derived from a single non terminal
   (S or A or B) and length of derived symbol/s is greater than or equal to the length of its derivative
   symbol (| AB | = | S |; | a | = | A |; | aA | = | A |; | bc | = | B |; | b B c| = | B |).
   Hence, the Grammar
   ({S, A, B}, {a, b, c}, S, P} is a CFG and the language is a CFL.

Example 11.8. A language L is defined over Σ = {a, b} such that it contains equal number of a’s
and b’s. Construct the grammar for above grammar and checks its ambiguity.
Sol. We see that the L contains following possible set of strings, i.e.,

1. strings starting with symbol a’s s.t. it has equal number of a’s and b’s


2. strings starting with symbol b’s s.t. it has equal number of b’s and a’s
   Let S be the starting symbol and A and B are other non terminals then following are the
   productions:
   Corresponds to 1: Corresponds to 2:
   S → a BS → b A
   B → b | b S | a B B A → a | a S | b A A
   Now derive the arbitrary string ‘abbaabab’ (that has equal number of a’s and b’s) from
   above set of productions, i.e.,

→

→