CFG for a^n b^3m c d^m e f^2n with m, n > 0

571 Views Asked by At

I want to find the CFG for this a^n b^3m c d^m e f^2n with m, n > 0

What I have so far

S -> A B C
A -> a A ff
B -> bbb B d
C -> c e

Does this make any sense?

2

There are 2 best solutions below

0
Nikolay Handzhiyski On

I think that this is the grammar:

; this rule generates "a" first and "ff" last
S = a A ff

; allow more "a" first and "ff" last
A = S

; between "a^n" and "f^2n" there will be "b^3m c d^m" followed by "e"
A = B e

; this rule generates "bbb" first and "d" last
B = bbb C d

; allow more "bbb" first and "d" last
C = B

; this rules generates "c" between "b^3m" and "d^m"
C = c
0
derpirscher On

Your grammar so far allows the c to come after the d which violates the rules.

The following should work

S = a S ff | a bbb B d e ff
B = bbb B d | c

The first rule guarantees, that for every a in the beginning there are two f in the end. It enforces at least one a. The second half enforces the sequence d e ff....

The second rule enforces the correct number of b and d and also that the single c is between the bs and the cs