ZuoTi.Pro
Question

6. 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 (10 points, 0.5 points for each of the first 8 blanks A aA A S abAI abcS Solution: The language generated by the given grammar is: L The given grammar is By factoring ab out from S abAI abcS, the given grammar can be converted to (1) This grammar can also be written as (2) Grammars (1) and (2) are both LL(1). To show (2) is LL(1), it is sufficient to consider ab and abcaba as input strings. In the following, show a unique leftmost derivation of the string abcaba using grammar (2). (6 points)

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

Homework Answers

Answer #1

The Hiven rmme Thip ra in right linea -/>-/m re La gri

0 0
Add a comment
Know the answer?
Add Answer to:
Use left-factoring to find an equivalent LL(k) grammar for the following grammar where k is as...
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

  • I would like to know if the following grammar for {c^m+n a^m b^n | m, n...

    I would like to know if the following grammar for {c^m+n a^m b^n | m, n elementof N} is an LL(2) grammar. S rightarrow ccSbb | cSb | T; T rightarrow cTa | and Use the string ccab to justify your answer. If your answer is YES, mark the YES box and show the leftmost derivation for the string ccab in the blanks below the YES box. Otherwise, mark the NO box and show a derivation that would lead to...

  • 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)-

  • 1. Consider the following grammar A - aB B-Sb (a) Show a derivation tree for the...

    1. Consider the following grammar A - aB B-Sb (a) Show a derivation tree for the string aabbbb using the grammar. (b) Give an English description of the language generated by the grammar 2. Let G be the grammar below: S-ASB ab | SS (a) Show that G is ambiguous. (b) Construct an unambiguous grammar equivalent to G. 3. Find a context free grammar for the language L3- fa"b"c+m :n,m21) 4. Find a context free grammar for the language L4...

  • Solve the E question.. Gr 114 D. Con vert the given grammar to an equivalent non-deterministic...

    Solve the E question.. Gr 114 D. Con vert the given grammar to an equivalent non-deterministic finite automata. 31. The grammar in Exercise 26. 32. The grammar in Exercise 28. 33. The grammar in Exercise 29. 34. The grammar in Exercise 30. E. The following grammar is not regular. Convert it to an equiva lent regular grammar. What h the language of the grammar? E. The following regular grammars are incorrect. Debug and correct them. 37. Binary numbers divisible by...

  • Please help me with the coding for LL(1)!! The given grammar was: P → PL |...

    Please help me with the coding for LL(1)!! The given grammar was: P → PL | L L → N; | M; | C N → print E M → print "W" W → TW | ε C → if E {P} | if E {P} else {P} E → (EOE) | V (note: this has a variable O) O → + | - | * V → 0 | 1 | 2 | 3 (note: this has a terminal...

  • Question Set 2 1. Given the following grammar dactor>-> ( <expr> ) a) What is the...

    Question Set 2 1. Given the following grammar dactor>-> ( <expr> ) a) What is the associativity of each of the operators? What is precedence of the operators? Show a leftmost derivation and parse tree for the following sentence: b) c) A-A(B(C A)) d) Rewrite the BNF grammar above to give precedence over and force to be right associative.

  • Rewrite Grammar with python Better pictures. this is only one question 2. Now we can begin on our LSystem clas...

    Rewrite Grammar with python Better pictures. this is only one question 2. Now we can begin on our LSystem class. First, we have to write a method that does the rewriting in the grammar. The idea here is that you start out with an axiom which is just a string. Then you apply rewrite rules, called productions, to expand some or all of the letters in the axiom to create a string, called a derived word. You can rewrite the...

  • Question Set 2 1. Given the following grammar dactor>-> ( <expr> ) a) What is the...

    Question Set 2 1. Given the following grammar dactor>-> ( <expr> ) a) What is the associativity of each of the operators? What is precedence of the operators? Show a leftmost derivation and parse tree for the following sentence: b) c) A-A(B(C A)) d) Rewrite the BNF grammar above to give precedence over and force to be right associative.

  • 2. Consider the following grammar:                         <assign> à <id> = <expr>       

    2. Consider the following grammar:                         <assign> à <id> = <expr>            <id>   à A | B | C            <expr> à <id> + <expr>                      | <id> * <expr>                      | ( <expr> )                      | <id> Show a parse tree and leftmost derivation for the following statements: (a)        A = ( A + B ) * C (b)        A = A * ( B + C ) 3. [10 Points] Show that the following grammar is...

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