ZuoTi.Pro
Question

Problem 1. Consider the grammar S → Y X Y X → a Y | Y...

Problem 1. Consider the grammar
S → Y X Y
X → a Y | Y
Y → b b Y | X | ε

where a and b are tokens. Remember that ε represents the empty string. Y → ε means that Y
does not have to match any tokens.

1. Give a leftmost derivation for the string (sequence of tokens):
bbabbabb

2. Give a rightmost derivation for the string (sequence of tokens):
bbabbabb

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1 

 
1)
S -> YXY -> bbYXY -> bbXY -> bbaYY -> bbabbYY -> bbabbXY -> bbabbaYY -> bbabbaY -> bbabbabbY -> bbabbabb

2)
S -> YXY -> YXX -> YXaY -> YXabbY -> YXabb -> YaYabb -> YabbYabb -> Yabbabb -> bbYabbabb -> bbabbabb
0 0
Add a comment
Know the answer?
Add Answer to:
Problem 1. Consider the grammar S → Y X Y X → a Y | Y...
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. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • 1) a. Write down an unambiguous grammar that generates the set of strings                         {...

    1) a. Write down an unambiguous grammar that generates the set of strings                         { s;, s;s, s;s;s;, . . . }       b. Give a leftmost and rightmost derivation for the string s;s; using your grammar.

  • Consider the following context-free grammar with terminals {a, b, c, d} and start symbol S. S...

    Consider the following context-free grammar with terminals {a, b, c, d} and start symbol S. S → W | X | Y | Z W → AW D | X | Y | Z X → BXD | Z Y → AY C | Z Z → BZC | ε A → a B → b C → c D → d (a) Give a derivation tree with input string: aaaabccddd (b) What language does this CFG recognize? Give a...

  • For both of the following languages, provide a grammar that generates it, an intuitive explanatio...

    Please actually answer it For both of the following languages, provide a grammar that generates it, an intuitive explanation why this grammar generates this language, and a graphical representation of a push-down automaton that recognizes this language. (a) The language of properly nested sets of parentheses over the alphabet G)). Note that the string (COO))) belongs to this language, while the string (O) () does not because the third closing parenthesis does not have a matching opening parenthesis. Provide a...

  • 3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa...

    3 points) Question Three Consider the context-free grammar S >SS+1 SS 1a and the string aa Give a leftmost derivation for the string. 3 points) (4 poiots) (5 points) (3 points) sECTION IWOLAttcmpt.any 3.(or 2) questions from this.scction Suppose we have two tokens: (1) the keyword if, and (2) id-entifiers, which are strings of letters other than if. Show the DFA for these tokens. Give a nightmost derivation for the string. Give a parse tree for the string i) Is...

  • 1.)    Consider the following grammar in which S, A, and B are nonterminal symbols and S...

    1.)    Consider the following grammar in which S, A, and B are nonterminal symbols and S is the start symbol. S → 1A | 0B A → A0 | 1B B → 10A| 1 Show that the grammar is ambiguous by showing two parse trees for the sentence 1110110 using leftmost derivation.

  • Given the following ambiguous context free grammar (3x20) 1. (a) Explain why the grammar is ambiguous...

    Given the following ambiguous context free grammar (3x20) 1. (a) Explain why the grammar is ambiguous (b) Find an equivalent unambiguous context-free grammar. (c) Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above. 2. Construct non-deterministic pushdown automata to accept the following language (20) 3. Convert the following CFG into an cquivalent CFG in Chomsky Normal Form (CNF) (20)-

  • Consider the following grammar: (//some alternative rules are listed on separate lines without using symbol |):...

    Consider the following grammar: (//some alternative rules are listed on separate lines without using symbol |): stmt −> assignment −> subr call assignment −> id := expr subr call −> id ( arg list ) expr −> primary expr tail expr tail −> op expr −> ε primary −> id −> subr call −> ( expr ) op −> + | - | * | / arg list −> expr args tail args tail −> , arg list −> ε...

  • Consider the following grammar (G1) for simple assignment statements. (The symbols in double quotation marks are...

    Consider the following grammar (G1) for simple assignment statements. (The symbols in double quotation marks are terminal symbols.) assign → id “ = ” expr id → “A” | “B” | “C” expr → expr “ + ” expr | expr “ ∗ ” expr | “(” expr “)” | id a) Give a (leftmost) derivation for string A = B ∗ A + C. b) Give the parse tree for string A = B ∗ A + C. c)...

  • Use left-factoring to find an equivalent LL(k) grammar for the following grammar where k is as...

    Use left-factoring to find an equivalent LL(k) grammar for the following grammar where k is as small as possible. Fill out the following blanks S rightarrow abA A rightarrow ab| Lambda Solution: The language generated by the given grammar is: L = _____ The given grammar is _____ By factoring ab out from S rightarrow abA | abcS, the given grammar can be converted to _____ _____ _____ (1) This grammar can also be written as _____ _____ _____ (2)...

  • 1.a    Consider  the following Grammar,                               

    1.a    Consider  the following Grammar,                                                                  <assign> à   <id> = <expr>     <id> à A | B |C    <expr> à < expr> + <expr>         | <expr> * <expr>                   | ( <expr> )                   | <id> Derive the following statement using leftmost derivation.   A = A * (B*(C+ A)) b. 2 a}.    Consider the following grammar that expresses parenthesized expressions of digits, including both addition and multiplication. <expr> := <expr> + <expr> | <expr> * <expr> | (expr>) | <digit> <digit> :=   0 | 1 | 2 |...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT