World's most popular travel blog for travel bloggers.

Chomsky form for language of single alphabet member

, , No Comments
Problem Detail: 

I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a}

My approach was

S -> AB | e A -> a 

Now here's the part I'm confused, how do I represent B? If B -> a then I get only even strings, if B -> e then it's not in normal form. :| Any help would be appreciated.

Asked By : Shelby. S
Answered By : vonbrand

The grammar is similar to what you say: $$ S \rightarrow S S \mid a $$ This can't generate $\epsilon$, which any true CFG can't.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback