Problem Detail: I am stuck and having a hard time with this question. I want to construct a CFG for the language $$L = {{a^lb^mc^n | l,min N, n=|l-m|}}$$ I know that the language consists of strings where:
1. number of a’s = number of b’s, so c=0
2. number of a’s more than number of b’s, c=l-m
3. number of a’s less than number of b’s, c=-(l-m)
I started with $$S->ab$$ $$S->aSb$$ This generates all of case one, where number of a’s = number of b’s and c=0. I know that I could increment a’s and c’s by having aSc but I cant put that in the second line because it could generate a(aSc)b which is not in the language.
1. number of a’s = number of b’s, so c=0
2. number of a’s more than number of b’s, c=l-m
3. number of a’s less than number of b’s, c=-(l-m)
I started with $$S->ab$$ $$S->aSb$$ This generates all of case one, where number of a’s = number of b’s and c=0. I know that I could increment a’s and c’s by having aSc but I cant put that in the second line because it could generate a(aSc)b which is not in the language.
Asked By : Data
Answered By : Denis
Hint: try to do each language separately, and then your final grammar is S->S1|S2|S3. To do your case 2, you can write $S->aSc|X$ $X->aXb|epsilon$. I.e. you start by generating the c’s and the exceeding a’s, and then you generate the b’s and the remaining a.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16678
