Need a detailed answer to this problem, since I need to understand how to work i

Question

Need a detailed answer to this problem, since I need to understand how to work it out on my own.

There is a computational task fstrings which have the same number of 0s and 1sh. Show the following: (i) Provide a Context Free Grammar to generate the language (ii) Show that every string in is generated from the Context Free Grammar (You may use strong induction on string length) (iii) Show that every string generated by Context Free Grammar is present in (You may use structural induction for this)

Explanation / Answer

1) S->aSb|bSa|SS|

2) lets take abab=> aSb(S->aSb)->abSab(s->bSa)->abab(S->)=>abab

3) S->aSb=>ab(equal no of a's and b's)

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---