CODEWITHSUNDEEP
context-free-grammarcontext-free-language
Corei7
Corei7

Reputation: 43

Context-free grammar for language describing a, ab, abc, ac...?

I'm trying to figure out what will be the CFG for a language described like that:

I tried this: S -> a | Sb | Sc

Or something like that:

S -> a | B | C

B -> Bb

C -> Cc

but it doesn't seem to work. Is there any other/better way to describe that language with a CFG?

Upvotes: 2

Views: 589

Answers (1)

Patrick87
Patrick87

Reputation: 28302

A grammar for for the language of strings which have a single a, and nothing else, is simply

S -> a

Your language is different in that zero or more b's and c's are also allowed. They can come before or after the single a and can come in any order. A grammar for the language "any number of b's and c's in any order' is

T -> bT | cT | e

Because we can have any number of b's and c's on either side of our single a, this suggests we can add the productions for nonterminal T to our production for S and change the production for S to derive a with a T on either side:

S -> TaT
T -> bT | cT | e

This grammar should work. Proving this grammar is correct is left as an exercise.

There are other viable approaches. One viable approach is to make a DFA for this regular language and then rewrite it as a grammar. The grammar will be context-free if this is done in a straightforward manner.

q0 -> bq0
q0 -> cq0
q0 -> aq1
q1 -> bq1
q1 -> cq1
q1 -> e

Upvotes: 1

Related Questions