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
Consider the following grammar S -> A M M -> S | A -> a E...
Consider the following grammar S -> A M M -> S | A -> a E | b A A E -> a B | b A | B -> b E | a B B Show a derivation for the string a b a a. Start with S => A M => ... and in each step replace one nonterminal by the right-hand side of a grammar rule until you end up with the symbols a b a a...
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
can someone please answer these in the correct format: Assignment #2 Total 43 pts (12pts) List...
can someone please answer these in the correct format: Assignment #2 Total 43 pts (12pts) List at least 3 words in the language and write regular expressions for the following: S = {a,b,c} L = {all words that have only one letter c in them} S = {a,b,c} L = {all words in which c’s appear in groups of two} S = {a,b,c} L = { all words that begin and end with the same letter} S = {a,b,c} L...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT