Please help design a CFG for each of the following languages 3. (30 points) Desi

Question

Please help design a CFG for each of the following languages

3. (30 points) Design a CFG for each of the following languages: a) Li-faipd| (i ), where i, j, k20} b) la = {aw | (it k), where i, j,k2 0} c) L3 = {aibick I (1J or ik), where i, j,k2 0} d) The set of all strings over alphabet (a,b) such that the mumber of a's is at least a many as the number of b's. e) The set of all strings over alphabet (a, b) that are of odd length. f) The set of all strings of a's and b's that are not of the for ww

Explanation / Answer

a. L1= {a^ib^jc^k | (i != j), where i,j,k>=0}

CFG is:

S1=> EC

E=> aEb | A | B

A=> aA | a

B=>bB | b

C=>cC |

Constraint is on the number of a's and b's. It should be either number of a's > number of b's or

number of a's < number of b's . There is no constraints on number of c's.

There in the grammar E is used to generate a and b and C to generate c.

E=> aEb, can generate equal number of a and b in the form of a^nEb^n

E=> A, generates only a's of any number ----> used to accept strings with more number of a's.

E=> B, generates only b's of any number ---> used to accept strings with more number of b's

b.

L2= {a^ib^jc^k | (i != k), where i,j,k>=0}

CFG is:

S=> aSc | AB | BC

A=> aA | a

B=>bB |

C=>cC | c

Constraint is on the number of a's and c's. It should be either number of a's > number of c's or

number of a's < number of c's . There is no constraints on number of b's.

S=> aSc, can generate equal number of a and c in the form of a^nSc^n

S=> AB, generates a's of any number followed by b's of any number ----> used to accept strings with more number of a's.

E=> BC, generates b's of any number followed by c's of any number ---> used to accept strings with more number of c's.

C. L3 is nothing but Union of L1 and L2.

Therefore CFG for L3 is

SS => S1 | S

Where S1 is CFG of Language L1 above in a part.

S is CFG of language L2 above in b part

D. Constraint here is number of a's should be equal to or greater than number of b's.. Therefore CFG is:

S=> aS | aSbS | bSaS |

S=> aS ---> used to accept strings with more number of a's

S=> aSbS and bSaS ---> used to accept strings with equal number of a's and b's

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.