Show that the language L = {awwR: w ∈ {a, b}*} is context-free.
Show that the language L = {awwR: w ∈ {a, b}*} is context-free.
Answer-
A language is context free language if it is generated by context free grammar. Therefore we generate grammar for given language. If grammar generated by language is context free grammar then given language will be context free language.
A language is context free language if it is generated by context free grammar. Therefore we generate grammar for given language. If grammar generated by language is context free grammar then given language will be context free language.
Language L = {awwR: w ∈ {a, b}*} is context-free.
Grammar for language(L)-
Grammar(G) = (V, Σ, P, S)
Where
V = {S,A}
Σ = {a, b},
P = { S→ aA , A → aAa , A → bAb , A →ε }
S={S} Starting symbol of grammar.
Context free grammar-
A grammar(G) is context free grammar if it is defined as
G = (V, Σ, P, S)
where
V= is a set of non-terminal symbols.
Σ= is a set of terminals
P= Production rule P: V → (V ∪ Σ)*
S=is the start symbol
According to definition of context free grammar the generated grammar (G) by language(L) is context free grammar. Hence language L = {awwR: w ∈ {a, b}*} is context-free.
Comments
Post a Comment