GATE Papers >> CSE >> 2017 >> Question No 37

Question No. 37 CSE | GATE 2017

Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are non-terminals.

$\style{font-family:'Times New Roman'}{\begin{array}{l}G_1:S\rightarrow\;aSb\vert T,T\rightarrow cT\vert\in\\G_2:S\rightarrow bSa\vert T,T\rightarrow cT\vert\in\end{array}}$

The language $\style{font-family:'Times New Roman'}{L(G_{1\;})\;\cap\;L(G_2)}$ is

Answer : (B) Not finite but regular.

Solution of Question No 37 of GATE 2017 CSE Paper

$ \begin{array}{l}\begin{array}{l}{\boldsymbol G}_\mathbf1\boldsymbol:\boldsymbol\;\;S\rightarrow\alpha sb\vert T,\;T\rightarrow cT\vert\in\\{\boldsymbol G}_\mathbf2\boldsymbol:\;\;S\rightarrow bSa\vert T,\;T\rightarrow cT\vert\in\\\;\;\;\;\;\;\;\;\;\;L\left(G_1\right)=\left\{\alpha^nc^mb^n\vert m,\;n\geq0\right\}\\\;\;\;\;\;\;\;\;\;\;L\left(G_2\right)=\left\{b^nc^m\alpha^n\vert m,\;n\geq0\right\}\\\;\;\;\;\;\;\;\;\;\;L\left(G_1\right)\cap\;L\left(G_2\right)=\left\{\alpha^nc^mb^n\right\}\cap\left\{b^nc^m\alpha^n\right\}\end{array}\\\;\;\;\;\;\;\;\;\;\;=\left\{c^m\vert m\geq0\right\}=c\ast\end{array} $

Since the only common strings will be those strings with only 'c', since in the first language all the other strings start with $'\alpha'$ and in the second language all the other strings start with 'b'.

Clearly the intersection is not finite but regular.

sBEwio levitra nizagara

Posted on  18/10/2020 20:03:36  by  dobsonz
RZr9aw viagra cialis buy

Posted on  01/11/2020 21:08:41  by  johnanx
J1OX8w write my essay

Posted on  04/12/2020 03:11:33  by  dobson
VM1Ubf xnxx videos

Posted on  12/12/2020 20:44:42  by  johnan

Posted on  13/12/2020 04:22:17  by  dobson

Posted on  15/12/2020 05:21:55  by  dobson

Posted on  09/01/2021 12:01:15  by  dobson
lIYAk2 waldorf doll

Posted on  09/01/2021 16:19:44  by  johnanz
Leave a comment