Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a.

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
I have created the following solution but its left recursive:
S--> a|bSc|cSb|Sbc

How to avoid the above problem.
Somebody please guide me.

Zulfi.
 

WBahn

Joined Mar 31, 2012
26,398
You REALLY need to start looking at your solutions and asking if they actually work!

It's one thing to miss subtle cases, but your solutions almost always miss lots of real obvious cases.

Using your solution, derive "ab" or "cba" or "abb" or "aa".
 

WBahn

Joined Mar 31, 2012
26,398
You are correct in that "aa" is not in the language. My bad.

I'll give you a hint, but I won't provide the answer. You have seen countless languages and the grammars that generate them and you are still missing something that prevents YOU from designing a grammar that generates a particular language. See yet one more grammar that generates a language is not likely to change that situation. YOU have to struggle and fight with doing it so that you can LEARN how to DESIGN a simple grammar. That is a very different skill then seeing how a grammar that generates a language (though a lot of exposure to the latter usually helps develop the ability to do the former).

You want your grammar to be able to recursively generate either b's or c's to the left or right and then end when it generates a single 'a'.

Since there is no requirement of b's relative to c's, you don't want or need any particular production to involve both.
 
Top