Cheap and Secure Web Hosting Provider : See Now

[Solved]: What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$

, , No Comments
Problem Detail: 

I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers.

Also, in general, are there any good methods or ways of thinking that help one to think of context free grammars that generate a given language. Any tips are much appreciated, thanks.

EDIT: I've tried S →ABCD, A →aA | λ, B →bB | λ, C →ccC | λ, D →dD | λ

However, this doesn't allow for always generating twice the amount of c's as there are a's.

Asked By : AmazingBergkamp

Answered By : Mahdi Dolati

For matching number of a and c you need to do something like this:

$$ S \rightarrow AB \\ A \rightarrow aAcc \\ A \rightarrow C \\ C \rightarrow bC | λ \\ B \rightarrow dB | λ $$

You need to produce them in one rule to be sure the ratio is kept.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35931

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback