next up previous
Next: Show that the language L Up: Elements of Answers for Exercise Previous: Elements of Answers for Exercise

Is the language L regular?

It is easy to prove by induction (on the number of rule applications from S to a word w $ \in$ L) that L is well parenthesized. We saw durig the course that well parenthesized languages (like arithmetic expressions) cannot be regular (by applying the pumping Lemma).


next up previous
Next: Show that the language L Up: Elements of Answers for Exercise Previous: Elements of Answers for Exercise
Marc Moreno Maza
2004-12-01