From: Introduction to Languages and the Theory of Computationproblem 6.5 states:

Question

From: Introduction to Languages and the Theory of Computationproblem 6.5 states:
In each case the productions in a CFG are given: Provethat neither one generates the language L = (x over {0,1}* | N0(x)= N1(x)} (Which means that the number of 0s and 1s in thelanguage are the same, if I'm not mistaken)
a) S -> S01S | S10S | lamda b) S -> 0S1 | 1S0 | 01S | 10S | S01 | S10 | lamda
I can't convince myself that these two CFGs don't produce thesame number of 0's and 1's! I'm sure I am mistaken but Ihaven't got a clue.

In each case the productions in a CFG are given: Provethat neither one generates the language L = (x over {0,1}* | N0(x)= N1(x)} (Which means that the number of 0s and 1s in thelanguage are the same, if I'm not mistaken)
a) S -> S01S | S10S | lamda b) S -> 0S1 | 1S0 | 01S | 10S | S01 | S10 | lamda
I can't convince myself that these two CFGs don't produce thesame number of 0's and 1's! I'm sure I am mistaken but Ihaven't got a clue.

Explanation / Answer

Dear member it will (a&b both) produce the languge inwhich o's and 1's are same number. think any string in which 0'sand 1's are not equal and try to produce it. you will not besucceed. So accept the result. for example i want to try to generate a string of (00011111)from it. a) can be written as    i) S -> S01S ii) S-> S10S iii) S-> lamda it states that you can replace yous with S01S or S10S or lamda. if you want to generate (00011111) you will notsucced. first break the string in pairs (00 01 11 11) now look can you generate 00 from the above no,we cannot generate .. Hope now you will convenced and will Rate Higher..

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.