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

Question No. 10 CSE | GATE 2017

Consider the following context-free grammar over the alphabet $\style{font-family:'Times New Roman'}{\sum=\{a,b,c\}}$ with S as the start symbol:

$\style{font-family:'Times New Roman'}{\begin{array}{l}S\rightarrow abScT\;\vert\;abcT\\T\rightarrow bT\;\vert\;b\end{array}}$

Which one of the following represents the language genrated by the above grammar?

(A) $\style{font-family:'Times New Roman'}{\{(ab)^n(cb)^n\vert n\geq1\}}$
(B) $\style{font-family:'Times New Roman'}{\{(ab)^ncb^{m_1}cb^{m_2}.....cb^{m_n}\vert n,m_1,m_2,....m_n\geq1\}}$
(C) $\style{font-family:'Times New Roman'}{\{(ab)^n\left(cb^m\right)^n\vert m,n\geq1\}}$
(D) $\style{font-family:'Times New Roman'}{\{(ab)^n\left(cb^n\right)^m\vert m,n\geq1\}}$

Answer : (B) $\style{font-family:'Times New Roman'}{\{(ab)^ncb^{m_1}cb^{m_2}.....cb^{m_n}\vert n,m_1,m_2,....m_n\geq1\}}$

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

Solution of Question No 10 of GATE 2017 CSE Paper

$ \begin{array}{l}S\rightarrow\alpha bScT\vert\alpha bcT\\T\rightarrow bT\vert b\end{array} $

Solving $T\rightarrow bb\ast$ will gives $b^+.$

Substitute in $S$ to get

$ S\rightarrow\alpha bScb^+\vert\alpha bcbb^+ $

So, solution of $S$ would be $ \left\{\left(\alpha b\right)^n\left(cb^+\right)^n\vert n\geq1\right\} $ which is nothing but $ \left\{\left(\alpha b\right)^ncb^{m1}cb^{m2}...cb^{m_n}\vert n,\;m_1,\;m_2...\;m_n\geq1\right\} $

Comments

LTKxjO http://pills2sale.com/ levitra nizagara

Posted on 18/10/2020 16:19:28 by dobsonz

QkKRcM http://pills2sale.com/ levitra nizagara

Posted on 18/10/2020 19:14:31 by dobsonz

Самая лучшая БК 1xbet ставки 1xbet скачать приложение на андроид Сейчас 1xbet – это самая известная букмекерская контора, в которой можно совершать ставки на спортивные события. А для того чтобы получить постоянный доступ на 1xbet скачать приложение , необходимо воспользоваться зеркалом 1xbet, которое все время обновляется. Данный ресурс был создан в 2007 году. Каждый год он становился только популярней и ему удалось зарекомендовать себя с хорошей стороны. Здесь возможно выполнить ставку на любой вид спорта и не только. Помимо спорта ресурс предлагает получать деньги на политике. Заработанные денежные средства возможно перевести на любой электронный кошелек или банковскую карту. Как я проверил на личном опыте, все переводы проходят очень быстро. Если имеется желание, то на ресурсе возможно не только выполнить ставку, но и следить за спортивным матчем онлайн. Плюсы букмекерской конторы Следует сразу же заметить, что эта контора обладает рядом несомненных преимуществ: • Постоянно на портале предоставляется много матчей, на которые можно сделать ставки. • Ставки совершаются в режиме онлайн. • Отличные коэффициенты. • Можно подобрать любое предложенное киберспортивное состязание и сделать на него ставку. • Срочный вывод денег. Благодаря этим 1xbet приложение android преимуществам у меня получилось заработать уже достаточно много денег. Ежели вам нужно 1xbet зеркало http://ivanovpavel.itinity.ru/node/8498 – это то, что Вы искали! Как пройти регистрацию в https://yasnotorg.ru/user/profile/12743 Зарегистрироваться в данной букмекерской конторе не сложно. Попав на портал, возможно смело приступать к регистрации. Для этого необходимо указать нужные параметры, а потом согласиться с условиями соглашения. Так, в учетной записи нет данных о человеке, и не нужно проходить верификацию. Новый игрок получит 100 евро на свой счет в качестве приветственного бонуса. На портал букмекерской конторы можно попасть посредством главной ссылки, но, к сожалению, ее часто блокируют. Поэтому понадобится воспользоваться зеркалами или ТОР браузером для обхода блокировок. Зеркало помогает обойти блокировку, при этом меняется только адрес ресурса, сам же портал будет таким же. Стоит выделить, что блокировка не говорит о том, что сайт является лохотроном. У букмекерской конторы имеются все лицензии, которые я самостоятельно изучил, когда проходил регистрацию на ресурсе. Просто-напросто лицензии выданы не в РФ, поэтому у нас в стране этот ресурс блокируется. Я давно делаю ставки в этой БК и еще ни разу не пожалел о том. Чаще всего я перехожу на сайт 1xbet через зеркало на сегодня. В таком случае, я получаю постоянный доступ на портал абсолютно всегда.

Posted on 13/11/2020 01:56:28 by Batts

5W9Zpg 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 01:00:25 by dobson

lptrtW 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 02:58:58 by dobson

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

Posted on 12/12/2020 20:16:28 by johnan

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

Posted on 12/12/2020 20:38:02 by johnan

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

Posted on 13/12/2020 05:11:11 by dobson

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

Posted on 13/12/2020 05:51:57 by dobson

5Vp18w https://writemyessayforme.web.fc2.com/#writemyessay

Posted on 15/12/2020 06:11:20 by dobson

4WTUtZ https://writemyessayforme.web.fc2.com/#writemyessay

Posted on 15/12/2020 06:51:48 by dobson

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

Posted on 09/01/2021 08:22:56 by dobson

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

Posted on 09/01/2021 08:41:58 by dobson

Hvehnl http://waldorfdollshop.us/ waldorf doll

Posted on 09/01/2021 12:36:43 by johnanz

hQXH55 http://waldorfdollshop.us/ waldorf doll

Posted on 09/01/2021 12:56:23 by johnanz

GATE Papers >> CSE >> 2017 >> Question No 10

Answer : (B) $\style{font-family:'Times New Roman'}{\{(ab)^ncb^{m_1}cb^{m_2}.....cb^{m_n}\vert n,m_1,m_2,....m_n\geq1\}}$

Questions of Context Free Grammars and Push-down Automata

About

Follow Us On

Contact Us

Search in Website