Need help for #1-#8. 1, Consider the language L lar by Im, n Corsaut a grammar G

Question

Need help for #1-#8.

1, Consider the language L lar by Im, n Corsaut a grammar G such that LIG) constucta segular grammar Gsuchtha LG) E L Construct grammar G such that LIG) 3 consider the language L Ins 4 Explain why there cannot exist reguw grammar Gsuchthat LIG)- La Liuu, Linu,Lr, and where L and Laare as defined above 6 Give a megular grammar that generates the stungs over a b, chin which the a's precede the bs, which in precede the c's, his possble eat there are no as, bs cs Consider the grammar Gwth producton rules BSA IA e, there are no production mules el tacAng grammar. equivalentessenta) stan symbol Hint see sector 42 the form V-A except s AltA in LIG) and wth an and the examples. 8 Give a regular expression for the language LIG where G is he grammarin quistien

Explanation / Answer

1)

Context-free Grammer:

S->aAbB

A->aA |

B-> bB |

2)

Regular grammer:

=> aa*bb*

3)

S-> aSb | ab

strings accepted are: ab, aabb, aaabbb, ..etc

4)

Because you can't write a finite state machine that will 'count' identical sequences of 'a' and 'b' symbols. In a nutshell, FSMs cannot 'count'. Try imagining such a FSM: how many states would you give to symbol 'a'? How many to 'b'? What if your input sequence has more?

Note that if you had n <= X with X an integer value you could prepare such FSM (by having one with a lots of states, but still a finite number); such language would be regular.

6)

Regular Expression:

=> a*b*c*

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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