Question

Consider the following grammar (A and B are non-terminals) A → A a | B |...

Consider the following grammar (A and B are non-terminals)

A → A a | B | B d

B → b d | b

Are there any ambiguities? If so, please give an example.

Homework Answers

Answer #1

Considering the grammers,the parse tree of the gramer is as follows,

A → A a | B | B d

B → b d | b

Here ,considering the string "bd",we get two parse tree using this grammer.

since two different parse tree exists,the grammer is ambigious.

A grammer is said to ambiguious ,if there is more than one Left most derivation or more than Right most derivation or more than one parse tree exists.Here the grammer is ambigiuous.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
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...
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 context-free grammar: S → TT | U T → 0T | T0 |...
Consider the following context-free grammar: S → TT | U T → 0T | T0 | # U → 0U00 | # a. Give a parse tree for the string: 0#0#0 b. Give a leftmost derivation for the string: 00#0000
The grammar below generates Boolean expressions in prefix notation: B → O B B | not...
The grammar below generates Boolean expressions in prefix notation: B → O B B | not B | id O → and | or a) Write an attribute grammar to translate Boolean expressions into fully parenthesized infix form. For example, expression and and a or b c d turns into the following fully parenthesized expression ((a and (b or c)) and d). b) Now write an attribute grammar to translate the Boolean expressions into parenthesized expressions in infix form without...
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...
True or False If a non-terminal symbol appears at the end of the right-hand side of...
True or False If a non-terminal symbol appears at the end of the right-hand side of a rule, its Follow set contains the entire Follow set of the symbol on the left-hand-side of the rule. If a grammar has no Nullable non-terminals, the Follow sets can be ignored when computing the predict table. If A → BaBa is a rule and First(B) = {a}, then Predict(A,a) should contain A → BaBa. If no cell of the predict table for a...
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...
Try to write a BNF like Grammar for each one of the following constructs: - positive...
Try to write a BNF like Grammar for each one of the following constructs: - positive and negative integer numbers - floating point numbers - variable names. Notice: Recursion is needed here (use right recursion): here is an example (a grammar of two rules defines any positive integer) : Note the length in digits is not defined in this grammar, it can go recursively for ever. So we need to add another annotation (a semantic part). <positive_Number> -> <digit> |...
Construct the LR parsing table for the following grammar: S → b b
Construct the LR parsing table for the following grammar: S → b b
Consider the grammar G with productions as follows: S → AD | BC A → a...
Consider the grammar G with productions as follows: S → AD | BC A → a B → b C → a | AS | BE D → b | BS | AF E → CC F → DD Use the CYK algorithm to test membership of abbaba.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT