CSE GATE 2017 Question No 37 Theory of Computation - Context Free Grammars and Push-down Automata

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

(A) Finite
(B) Not finite but regular.
(C) Context-Free but not regular
(D) Recursive but not context-free

Answer : (B) Not finite but regular.

GATE 2017 CSE Theory of Computation Context Free Grammars and Push-down Automata

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.

Comments

sBEwio http://pills2sale.com/ levitra nizagara

Posted on 18/10/2020 20:03:36 by dobsonz

RZr9aw http://pills2sale.com/ viagra cialis buy

Posted on 01/11/2020 21:08:41 by johnanx

J1OX8w https://www.quora.com/What-the-top-SEO-keywords-for-essay-you-know/answer/Alan-Smith-1772 write my essay

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

VM1Ubf http://xnxx.in.net/ xnxx videos

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

lDXwIB https://writemyessayforme.web.fc2.com/

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

7GIzNG https://writemyessayforme.web.fc2.com/#writemyessay

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

mnV67J https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

Posted on 09/01/2021 12:01:15 by dobson

lIYAk2 http://waldorfdollshop.us/ waldorf doll

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

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

Answer : (B) Not finite but regular.

Questions of Context Free Grammars and Push-down Automata

About

Follow Us On

Contact Us

Search in Website