CODEWITHSUNDEEP
compiler-constructioncontext-free-grammarformal-languages
Joachim
Joachim

Reputation: 21

CFG grammar definition

Define a CFG (context free language) that generates the language:

L={a^n b^m c^n | n,m>=0}

Can anyone tell me how to address the problem?

My understanding is that L is made of elements like: { aabbbcc } (I assumed that n=2 and m=3)

thanks in advance Joachim

Upvotes: 2

Views: 474

Answers (2)

emi
emi

Reputation: 5410

Consider a context-free grammar that generates the language

L1 = {a^nc^n : n >= 0}

such as

G1 = <{S},{a,c},S,{S -> aSc,S-> λ}>

Derivations in G1 can be characterized as follows:

G1 =>1 S        (via S)
   =>* a^nSc^n  (via n >= 0 applications of S -> aSc)
   =>1 a^nc^n   (via S -> λ)

The grammar G1 establishes the required relationship between the number and placement of a's and c's in the language L1, then terminates with an application of the rule S -> λ.

Consider how a derivation in G1 is terminated by applying the rule S -> λ, and how you might generate a sequence of m >= 0 b's instead of the empty string. Here is a solution to the problem that is slightly more general. Suppose we have a language L2 generated by the grammar

G2 = <V,N,S2,P>

In order to generate strings in L2 surrounded by an equal number of a's and c's, the rules of G1 might be augmented as follows to obtain a grammar G1':

G1' = <{S} ∪ V,{a,c} ∪ N,S,{S -> aSc,S -> S2} ∪ {P}>

To solve your problem, let L2 be the language {b}* and G2 the regular grammar that generates it.

Upvotes: 0

Jim Lewis
Jim Lewis

Reputation: 45115

This sounds like homework, so I'll just give a few hints.

How might you make the number of a's and c's match in a context-free grammar production?

What kind of production could you use to generate a sequence of b's?

How could these two subproblems be combined into a single context-free grammar?

Upvotes: 2

Related Questions