Cheap and Secure Web Hosting Provider : See Now

[Solved]: Build a context-free grammar for a context-free language

, , No Comments
Problem Detail: 

A context-free language is defined by its description:

$L=(a^{2k} \space b^n \space c^{2n} \mid k \geq 0, \space n > 0)$

For example:

$bcc, aabcc, aabbcccc, bbcccc$

How to build a context-free grammar for this context-free language?

I suppose that the order for generating any chain in this problem matters: 'b' will always stand after 'a' and 'c' - after 'b'. Is it so?

My attempts leaded to this solution:

$ S \rightarrow aaAbcc \mid bAcc \mid aabAcc $

$ A \rightarrow aa \mid bcc \mid λ $

Please correct me if I'm wrong or better offer your solution to this problem.

Asked By : Happy Torturer

Answered By : sai_preet

$ S \rightarrow EG $ , $ E \rightarrow aO \mid λ $ , $ O \rightarrow aE $ , $ F \rightarrow bFcc \mid λ $, $ G \rightarrow bFcc $ . I am assuming $λ$ stands for empty string.

Better one:

$ S \rightarrow EF $ , $ E \rightarrow aO \mid λ $ , $ O \rightarrow aE $ , $ F \rightarrow bFcc \mid bcc $.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback