Cheap and Secure Web Hosting Provider : See Now

[Answers] Proving a language is context free by coming up with a context free grammar for the language

, , No Comments
Problem Detail: 

Let A and B be languages over $\sum$ = {0, 1, 2, 3}

Language A = {$(0U1)^a(1U2)^b(2U3)^c | a \geq b$}

Language B = {$(0U1)^a(1U2)^b(2U3)^c | a = c$}

Question: prove that A and B are context free

Asked By : user14864

Answered By : Ryan Smith

The grammar for language B appears correct. But the grammar for language A is incorrect. This grammar will produce strings that are out of order and not in the language. Try:

$S\rightarrow AB$

$A\rightarrow (0U1)A|(0U1)A(1U2)|\epsilon$

$B\rightarrow (2U3)B|\epsilon$

My idea was to break it up into two sections and just deal with those.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback