Question

Given the following grammar and the right sentential form, draw a parse tree and then specify...

Given the following grammar and the right sentential form, draw a parse tree and then specify and write the phrases, simple phrase(s), and the handle.

Grammar: S → aAb | bBA A →

ab | aAB

B → aB | b

Sentential form: aaababb

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

Homework Answers

Answer #1

Q.Given the following grammar and the right sentential form, draw a parse tree and then specify and write the phrases, simple phrase(s), and the handle.

Grammar: S → aAb | bBA A →

ab | aAB

B → aB | b

Sentential form: aaababb

Answer:

a. aaAbb
Parse Tree:
 
                    S
                  / | \
                 a  A  b
                   /|\
                  a A B
                      |
                      b
 
Handles:        b, aAB
Phrases:        aaAbb, aaABb, aAb
Simple Phrase:  b
 
b. bBab
Parse Tree:
 
                    S
                  / | \
                 b  B  A
                      / \
                     a   b
 
Handles:        ab
Phrases:        bBab, bBA
Simple Phrase:  ab
 
c. aaAbBb
   aaAbBb --> aSBb --> aSBB --> x
or aaAbBb--> aaAbBB --> aSBB --> x
 
Therefore the last string can not be derived from the given grammar.
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
Given the following grammar and the right sentential form, draw a parse tree and then specify...
Given the following grammar and the right sentential form, draw a parse tree and then specify and write the phrases, simple phrase(s), and the handle. Grammar: S → AbB | bAc A → Ab | aBB B → Ac | cBb | c Sentential form: AbcacAbcbccb
Draw the parse tree for regular expression bb*+ab*(a+b).
Draw the parse tree for regular expression bb*+ab*(a+b).
Obtain a grammar in Chomsky Normal Form (CNF) equivalent to the grammar G with productions P...
Obtain a grammar in Chomsky Normal Form (CNF) equivalent to the grammar G with productions P given S ->aAb | B A ->aA | a B-> bB | b
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))
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...
Assignment-I Do the Lexical Analysis and draw the parse tree in the syntax analysis for the...
Assignment-I Do the Lexical Analysis and draw the parse tree in the syntax analysis for the following source code statement                        “ Sum : = PI + r1 * r2*80 “ Draw the transition diagram and transition table for NFA that recognizes the language:                     (a | b)* aabbb If x and y are strings ; write the answers for the following if x=”Hello” and y=”Welcome” : x2y4= xy2  =   x5 y.epsilon =
10. Draw and decorate the parse tree for the following Attribute Grammar for the following statement:...
10. Draw and decorate the parse tree for the following Attribute Grammar for the following statement: word = 2.0 ∗ (5 − 10) *** Assign is your STARTING SYMBOL Assign =: identifier = Expr Expr =: Expr + Term | Expr - Term | Term Term =: Term * Factor | Term / Factor | Factor Factor =: "(" Expr ")" | integer | float | identifier Assign =: identifier = Expr [ identifier.value <= Expr.value ] Assign =: identifier...
1. Given the Grammar <expr> --> <expr> + <term> | <term> <term> --> <term> * <factor>...
1. Given the Grammar <expr> --> <expr> + <term> | <term> <term> --> <term> * <factor> | <factor> <factor> --> ( <expr> ) | number For the given string 3 * ( 2 + 5 * 6), perform the following: 1. Left-most derivation 2. Draw a parse tree 3. Draw an abstract syntax tree Note: number as a terminal has multiple values
1. Draw a GTG (generalized transition graph) for the following right-linear regular grammar. S -> abA...
1. Draw a GTG (generalized transition graph) for the following right-linear regular grammar. S -> abA A -> baB B->aA | bb a)  Find a left-linear grammar for the language in the previous question.
Convert the grammar G = ({S,A,B,C},{a,b},P,S), where P is given below, into the Chomsky Normal Form....
Convert the grammar G = ({S,A,B,C},{a,b},P,S), where P is given below, into the Chomsky Normal Form. S −→ AaA | AB A −→ BB | bAA | ε B −→ bS | b | ε
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT