I. Give parse trees and derivations for each string a. a c. a+a+a b. ata Answer
ID: 3741576 • Letter: I
Question
I. Give parse trees and derivations for each string a. a c. a+a+a b. ata Answer each part for the following context-free grammar G T. a. What are the variables of G? b. What are the terminals of G c. Which is the start variable of G? d. Give three strings in L(G). e. Give three strings not in L(G) f. True or False: T = aba g. True or False: Taba. h. True or False: TT. i. True or False: T j. True or False: XXX aba. k. True or False: X l. True or False: T m. True or False: T n. True or False: SE. o. Give a description in English of aba XX. xxx L(G)Explanation / Answer
Answer for 1
For a)
a explanation
E -> T -----------------------------------------------------------------------------------------àE can be T
-> F ------------------------------------------------------------------------------------------àT can be F
-> a ----------------------------------------------------------------------------------------àF can be a
For b)
a+a
E -> E+T --------------------------------------------------------------------------------à E can be E+T
-> T+F --------------------------------------------------------------------------------------àE can be T and T can be F
-> F+a --------------------------------------------------------------------------------------àT can be F and F can be a
-> a+a --------------------------------------------------------------------------------------àF can be a
For c)
a+a+a
E -> E+T ---------------------------------------------------------------------------------------àE can be E+T
-> E+T+F --------------------------------------------------------------------------------àE can be E+T and T can be F
-> T+F+a ---------------------------------------------------------------------àE can be T, T can be F and F can be a
-> F+a+a ------------------------------------------------------------------------------à T can be F and F can be a
-> a+a+a ----------------------------------------------------------------------------------à F can be a
d) ((a))
E -> T // E can be T
-> F // T can be F
-> (E) --------------------------------------------------------------------------------------?> F can be (E)
-> (T) --------------------------------------------------------------------------------------?> E can be T
-> (F) --------------------------------------------------------------------------------------?> T can be F
-> ((E)) --------------------------------------------------------------------------------------?> F can be (E)
-> ((T)) --------------------------------------------------------------------------------------?> E can be T
-> ((F)) --------------------------------------------------------------------------------------?>T can be F
-> ((a)) --------------------------------------------------------------------------------------?> F can be a
Answer for II:
For a)
Here the R, X, S, T are the variables
For b)
Here the terminal of g is a,& b
For c)
Here the start variable of G is R
For d)
three strings in L(G) is .
R -> S -> aTb -> ab (T is replaced with epsilon)
R -> S -> bTa -> ba (T is replaced with epsilon)
R -> XRX -> aSb -> aaTbb -> aabb (T is replaced with epsilon)
For e)
three strings not in L(G)
a
b
aa
for f)
Here T => aba
False.
T => XTX => aXa => aba (We had to make 3 operations)
For g)
Then T => aba with *
True.
* above arrow represents any number of operations. We can do it in 3 operations
For h)
T => T
False.
There is no such operation in grammar
For i)
T => T with *
False
We cannot derive T from T
For j)
XXX => aba with *
True
X can be a or b
For k)
X => aba with *
False
For l)
T => XX with *
True
T => XTX => XX (Replace T with epsilon)
For m)
T => XXX with *
True
T => XTX => XXX
For n)
S => epsilon with *
False