Question

Ex#6: Prove the following grammar is ambiguous. <S> --> <A> <A> --> <A> + <A> <A>...

Ex#6: Prove the following grammar is ambiguous.
<S> --> <A>
<A> --> <A> + <A>
<A> --> <id>
<id> --> a | b | c

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1 

Let's generate a string a+b+c using given grammar.

Using left most derivations
<S> -> <A> -> <A>+<A> -> <A>+<A>+<A> -> <id>+<A>+<A> -> a+<A>+<A> -> a+<id>+<A> -> a+b+<A> -> a+b+<id> -> a+b+c

Using left most derivations
<S> -> <A> -> <A>+<A> -> <id>+<A> -> a+<A> -> a+<A>+<A> -> a+<id>+<A> -> a+b+<A> -> a+b+<id> -> a+b+c

since we can generate a+b+c with 2-different left most derivations, this grammar is ambiguous.
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Ex#5: Given the following grammar for a simple assignment statements. <assign> --> <id> = <expr> <id>...
Ex#5: Given the following grammar for a simple assignment statements. <assign> --> <id> = <expr> <id> --> A | B | C <exp> --> <id> + <expr> | <id> * <expr> | (<expr>) | <id> Show a leftmost derivation and a parse tree of the following statement: A = A *(B + (C * A))
Q1) (8%) Show a leftmost derivation step by step (each step on a single line)          ...
Q1) (8%) Show a leftmost derivation step by step (each step on a single line)           for the statement: A = A + B * C using the following grammar: <assign> --> <id> = <expr> <expr>    --> <id> + <expr> | <id> * <expr> |   <id> <id>         --> A | B | C Q2) (6%) Is this grammar ambiguous (Yes or No?) Justify your answer. Q3) (6%) Does this grammar enforce the precedence of the conventional operators  (Yes or No?)   Justify...
Show a leftmost derivation step by step (each step on a single line)           for the...
Show a leftmost derivation step by step (each step on a single line)           for the statement: A = A + B * C using the following grammar: <assign> --> <id> = <expr> <expr>    --> <id> + <expr> | <id> * <expr> |   <id> <id>         --> A | B | C Is this grammar ambiguous (Yes or No?) Justify your answer. Does this grammar enforce the precedence of the conventional operators  (Yes or No?)   Justify your answer.
Consider the following grammar. Nonterminals are lowercase and terminals are uppercase. s -> c A c...
Consider the following grammar. Nonterminals are lowercase and terminals are uppercase. s -> c A c -> c B | B Which of the following sentences is in the language generated by the grammar? a) BAA b) BBBA c) BBAAAAA d) none of the above
Construct the LR parsing table for the following grammar: S → b S b
Construct the LR parsing table for the following grammar: S → b S b
Construct the LR parsing table for the following grammar: S → a S a
Construct the LR parsing table for the following grammar: S → a S a
Question 1 Consider the following grammar G: S ➝ A B C | A C |...
Question 1 Consider the following grammar G: S ➝ A B C | A C | A | B A ➝ a B B ➝ b C | a C ➝ c D D ➝ d A Recall that a non-terminal A is reachable if there is a derivation starting from S in which A appears: S ⇒* x A y holds for some x and y which are sequences of terminals and non-terminals (possibly empty). For example, if there...
Construct the LR parsing table for the following grammar: S → b b
Construct the LR parsing table for the following grammar: S → b b
Automata Theory and Formal Languages Problems 1: Consider the following two grammars. Grammar G1- S →...
Automata Theory and Formal Languages Problems 1: Consider the following two grammars. Grammar G1- S → aSb / ∈ Grammar G2- S → aAb / ∈, A → aAb / ∈ a. is G1=G2 b. What is the grammar generated by the expression Problem 2: Let us consider the grammar. G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } ) Derive aaabbb Problem 3: Suppose we have the following grammar. G: N...
Given the grammar <expr> -> <term> {( + | - ) <term>} <term> -> <factor> {(...
Given the grammar <expr> -> <term> {( + | - ) <term>} <term> -> <factor> {( * | / ) <factor>} <factor> -> <exp> { ** <exp>} <exp> -> (<expr>) | <id> <id> = (A | B | C | D | E) leftmost derivation of A**B + (B * C)
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT