Question: Let the input alphabet be = { a b c } and L be the language of all words in which all the a's
Let the input alphabet be Σ = { a b c } and L be the language of all words in which all the a's come before the b's and there are the same number of a's as b's and arbitrarily many c's that can be in front, behind, or among the a's and b's. Some words in L are abc, caabcb, ccacaabcccbccbc.
(i) Write out all the words in this language with six or fewer letters.
(ii) Show that the language Lis not regular.
(iii) Find a PDA (deterministic) that accepts L.
(iv) Find a CFG that generates L.
Step by Step Solution
3.44 Rating (157 Votes )
There are 3 Steps involved in it
i All the words in this language with six or fewer let... View full answer
Get step-by-step solutions from verified subject matter experts
