CODEWITHSUNDEEP
context-free-grammarcontext-free-language
sarkle
sarkle

Reputation: 23

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

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?

Upvotes: 1

Views: 706

Answers (2)

derpirscher
derpirscher

Reputation: 17407

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

Upvotes: 0

Nikolay Handzhiyski
Nikolay Handzhiyski

Reputation: 1579

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

Upvotes: 0

Related Questions