CODEWITHSUNDEEP
context-free-grammarregular-languagensregularexpressioncontext-free-languageautomata-theory
zephyrus
zephyrus

Reputation: 1

what is the Context-Free Grammar for the following language?

Here is the language and I want to create a context-free grammar for it:

b(bc+a)*a(a+b)*c*

Here is my answer but I don't know if it's right or not:

S → bAaB
A → bcA | aA | epsilon
B → cB | aB | epsilon

Upvotes: 0

Views: 188

Answers (1)

derpirscher
derpirscher

Reputation: 17397

See the grammar below. It might be possible to simplify it a bit, but it should do the trick.

S -> bAaBC
A -> bcCaA | epsilon 
B -> aDbB | epsilon 
C -> cC | epsilon 
D -> aD | epsilon

The A rule allows one b followed by any number (but at least one) c followed by a single a. And this can occur any number of times (also zero)

The B rule allows any number (but at least one) of a followed by a single b. Again the whole expression can occur any number of times.

The C rule allows any number of c. This is used for the c* at the end of the word but also for the c+ in the first part (ie it's used in rule A)

The D rule allows any number of a. It's just a helper in rule B to accept the a+ in the second part of the word.

Upvotes: 0

Related Questions