Use the string “00111” to show that the following grammar is ambiguous: 𝑆 → 𝐴𝑆 | ϵ 𝐴 → 𝐴1 | 0𝐴1 | 01
Question
Use the string “00111” to show that the following grammar is ambiguous:
S → A S | ϵ
A → A 1 | 0 A 1 | 01
Solution
The given string is "00111". The grammar is ambiguous if there is more than one derivation tree that leads to the same string. Let's see if we can derive the string in two different ways.
First derivation:
- S -> AS (using S -> AS)
- AS -> 0A1S (using A -> 0A1)
- 0A1S -> 00A11S (using A -> 0A1)
- 00A11S -> 00111S (using A -> 01)
- 00111S -> 00111 (using S -> ϵ)
Second derivation:
- S -> AS (using S -> AS)
- AS -> 0A1S (using A -> 0A1)
- 0A1S -> 01S (using A -> 01)
- 01S -> 011S (using S -> AS and A -> 01)
- 011S -> 0111S (using S -> AS and A -> 01)
- 0111S -> 00111 (using S -> ϵ)
As we can see, there are two different derivations for the same string "00111". Therefore, the given grammar is ambiguous.
Similar Questions
Use the string “00111” to show that the following grammar is ambiguous: 𝑆 → 𝐴𝑆 | ϵ 𝐴 → 𝐴1 | 0𝐴1 | 01
Which one of the followings is equal to ⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜00000100⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟(00000100) ?
Use the string “ababab” to show that the following grammar is ambiguous: 𝑆 → 𝑆𝑆 | 𝑇 𝑇 → 𝑎𝑇𝑏 | 𝑎𝑏
Look at the sequence ଵଷ, ଶସ, ଷହ , ସ , … , … ..Write down (a) the 10th term (1 mark)(b) the nth term
Which of the following is an invalid statement? xyz = 1,000,000 x y z = 1000 2000 3000 x,y,z = 1000, 2000, 3000 None of these
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.