Context free grammar
Question:
Answer each part for the following context-free grammar G. R → XRX | S S → aT b | bT a T → XT X | X | ε X → a | b
very important : if you know how to answer these questions. leave your email and i will contact you or come here at 5 pm (new york time) you will answer similar questions. the point of asking this question is to be able to connect with someone who knows the topic
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: T ∗⇒ aba.
h. True or False: T ⇒ T .
i. True or False: T ∗⇒ T .
j. True or False: XXX ∗⇒ aba.
k. True or False: X ∗⇒ aba.
l. True or False: T ∗⇒ XX.
m. True or False: T ∗⇒ XXX.
n. True or False: S ∗⇒ ε.
o. Give a description in English of L(G).
Answer-a)
Variables of grammar(G)-(R,X,S,T)
Answer-b)
Terminals of grammar(G)-{a,b}
Answer-c)
Starting variable of grammar(G)-{R}
Answer-d) Three strings of L(G)-
Three strings are {ab,aab,abb}
Answer-e) Three strings are not in L(G)-{ a,b,aa,bb}
Answer-f)
False
Answer-g)
True
Answer-h) True
Answer-i) True
Answer-j) True
Answer-k) False
Answer-l) True
Answer-m) True
Answer-n) False
Answer-o) Description in English of L(G)-If S is the start symbol, R is useless symbol and L(G) is the set of all strings over a,b that have length bigger or equal 2, and the first symbol is always different than the last one. If R is the start symbol, L(G) consists of all strings over a,b that are not palindromes
Context-free grammar G is
R → XRX | S , S → aT b | bT a ,T → XT X | X | ε , X → a | b
The grammar(G) is defined as (V,Σ,P,S)
Where
V-is variables i.e. {R,X,S,T}
Σ-is terminals i.e. {a,b}
P-is production rule i.e. {R → XRX | S , S → aT b | bT a ,T → XT X | X | ε , X → a | b}
S-is starting symbol i.e. {R}
Answer-a)
Variables of grammar(G)-(R,X,S,T)
Answer-b)
Terminals of grammar(G)-{a,b}
Answer-c)
Starting variable of grammar(G)-{R}
Answer-d) Three strings of L(G)-
String i) R → XRX=>aRX=>aRb=>aSb=>aTb=>ab
String ii) R → XRX=>aRX=>aRb=>aSb=>aTb=>aXb=>aab
String ii) R → XRX=>aRX=>aRb=>aSb=>aTb=>aXb=>abb
Therefore three strings are {ab,aab,abb}
Answer-e) Three strings are not in L(G)-{ a,b,ε}
Answer-f)
False: because T derives aba in more than one steps.
T → XTX=>aTX=>aXX=>abX=>aba
Answer-g)
True :
T → XTX=>aTX=>aXX=>abX=>aba
Therefore T ∗⇒ aba.
Answer-h) True : T ⇒ T because T → XT X
Answer-i) True : T ∗⇒ T because T → XT X=>T → XXT XX=>......XXXXXTXXXXX
Answer-j) True XXX ∗⇒ aba. because XXX=>aXX=>abX=>aba. Therefore XXX ∗⇒aba
Answer-k) False: X ∗⇒ aba. because either X → a or X → b . Therefore X can not derive X ∗⇒ aba
Answer-l) True : T ∗⇒ XX. because T → XTX=>XX. Therefore T ∗⇒ XX is true.
Answer-m) True : T ∗⇒ XXX. because T → XTX=>XXX . Therefore T ∗⇒ XXX is true.
Answer-n) False : S ∗⇒ ε. because S can not derive ε.
Answer-o) Description in English of L(G)-If S is the start symbol, R is useless symbol and L(G) is the set of all strings over a,b that have length bigger or equal 2, and the first symbol is always different than the last one. If R is the start symbol, L(G) consists of all strings over a,b that are not palindromes.
Comments
Post a Comment