Knowee
Questions
Features
Study Tools

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
🧐 Not the exact question you are looking for?Go ask a question

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:

  1. S -> AS (using S -> AS)
  2. AS -> 0A1S (using A -> 0A1)
  3. 0A1S -> 00A11S (using A -> 0A1)
  4. 00A11S -> 00111S (using A -> 01)
  5. 00111S -> 00111 (using S -> ϵ)

Second derivation:

  1. S -> AS (using S -> AS)
  2. AS -> 0A1S (using A -> 0A1)
  3. 0A1S -> 01S (using A -> 01)
  4. 01S -> 011S (using S -> AS and A -> 01)
  5. 011S -> 0111S (using S -> AS and A -> 01)
  6. 0111S -> 00111 (using S -> ϵ)

As we can see, there are two different derivations for the same string "00111". Therefore, the given grammar is ambiguous.

This problem has been solved

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

1/1

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.