Programmer's End

1. Construct CFG for the following Languages: a) Set of all binary strings where number of 0’s are greater than number of 1’s. 2. Prove that the following CFGs are ambiguous: a) 𝑆 → 𝑎𝑆𝑏 | 𝑆𝑆| 𝜖 b) 𝑆 → 𝑆𝑎𝑆 |𝑆𝑏𝑆 |𝑐 c) 𝑆 → 𝑎𝐵 | 𝑎𝑏, 𝐴 → 𝑎𝐴𝐵|𝑎, 𝐵 → 𝐴𝐵𝑏 |𝑏 3. Convert the following CFGs into their equivalent Chomsky Normal Form: a) 𝑆 → 𝐵𝑆𝐵 | 𝐵 𝜖, 𝐵 → 00 𝜖 b) 𝑆 → 𝑏𝐴 |𝑎𝐵 , 𝐴 → 𝑏𝐴𝐴|𝑎𝑆 𝑎 , 𝐵 → 𝑎𝐵𝐵 | 𝑏𝑆 | b For Solutions Click in the Download Button: Download Solutions