Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
    G1 : S → aSb / T, T → CT | ∈
    G2 : S → bSa \ T, T → cT | ∈
    The language L(G1) ∩ L(G2) is
    1. Finite.
    2. Not finite but regular.
    3. Context-Free but not regular.
    4. Recursive but not context-free.
Correct Option: B

The context free grammar given over alphabets
∑ = {a, b, c}, with S and T are nonterminals.
Given, G1 : S → aSb | T , T → cT | ∈
G2 : S → bSa | T , T → cT | ∈
Lets L(G1) is the language for Grammar (G1) and L(G2) is the language for Grammar (G2).
where L(G1) = { an cm bn | m , n ≥ 0 }
L(G2) = { bn cm an | m , n ≥ 0 }
then L(G1) ∩ L(G2) = { an cm bn } ∩ { bn cm an }
= { cm | m ≥ 0 } = C*
Since the only common strings will be those strings with only ‘C’, so the intersection is not finite but regular.



Your comments will be displayed only after manual approval.