Context Free Grammar BNF

387 views Asked by At

need help with a non-extended BNF grammar:

Σ = {a,b,c}

L = {ω ɛ Σ^* | such that all a's (if any) comes before all c's(if any)}

For example, the strings aba, cbc, and abacbc are in the language, but string abcabc is not.

This is what i have so far (is it correct ? please correct me if i am wrong):

s->asbsc|bsasc|ascsb|ɛ

2

There are 2 answers

0
Chris Dodd On BEST ANSWER

Your comment says you want equal numbers of a and c, so start with the simple grammar that does that:

S -> aSc | ε

and add in any number of b's before/after/between those:

S -> BaScB | B
B -> Bb | ε

note that the above is not ambiguous (it's even LR(1)).

If you want to allow a different number of a's and c's, you can use the same approach to avoid ambiguity. Start with just the a's and c's:

S -> AC
A -> Aa | ε
C -> Cc | ε

and add in b's at the beginning and after each other character:

S -> BAC
A -> AaB | ε
C -> CcB | ε
B -> Bb | ε
0
Matt On

Do the number of a's and c's need to be the same? If, not then you are missing those cases where they differ, such as: aac. I think something like this should work:

S -> AC
A -> aA | bA | ε
C -> bC | cC | ε

The A production is used for deriving a sequence of characters that are not a c and the C production is used for deriving a sequence of characters that are not an a.