GATE Papers >> CSE >> 2019 >> Question No 58

Question No. 58 CSE | GATE 2019

Let $\mathrm\Sigma$ be the set of all bijections from {1, … , 5} to {1, … , 5}, where $id$ denotes the identity function, i.e. $ id(j)=j,\;\forall j $. Let $\circ$ denote composition on functions. For a string $ x=x_1\;x_2\;\dots\;x_n\in\mathrm\Sigma^n,\;n\leq0 $ , let $ \pi(x)=x_1\circ x_2\;\circ\dots\circ\;x_n $. Consider the language $ L=\{x\in\mathrm\Sigma^\ast\vert\pi(x)=id\} $. The minimum number of states in any DFA accepting $L$ is .


Answer : 120 to 120


Solution of Question No 58 of GATE 2019 CSE Paper

120)

The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements. The starting state will be "id" state, named as $ \begin{pmatrix}\begin{array}{c}12345\\12345\end{array}\end{pmatrix} $ and from there n! arrows will go the n! states each named with a distinct permutation of the set {1, 2, 3, 4, 5}. Since composition of permutation function is closed every arrow has to go to some permutation and hence some state.

Since the language only has those strings where $ \mathrm\pi\left(\mathrm x\right)= $ id only the starting state ("id" state) will be the final state. Sample machine with only 2 states is shown below

 

Comments
JDF9Ho http://pills2sale.com/ levitra nizagara

Posted on  18/10/2020 13:19:16  by  dobsonz
mXBwb9 http://pills2sale.com/ levitra nizagara

Posted on  18/10/2020 18:59:40  by  dobsonz
jbxFpJ http://pills2sale.com/ viagra cialis buy

Posted on  01/11/2020 19:16:06  by  johnanx
Лучшая букмекерская контора 1xbet ставки 1xbet скачать приложение На сегодня 1xbet – это одна из популярных букмекерская контора, в которой возможно совершать ставки на спорт. А для того чтобы получить бесперебойный доступ на приложения 1xbet на андроид бесплатно , нужно пользоваться зеркалом 1xbet, которое все время обновляется. Этот портал был запущен в 2007 году. Каждый год он становился лишь известнее и ему удалось зарекомендовать себя с хорошей стороны. Тут можно сделать ставку на любой вид спорта и не только. Помимо спорта сайт дает возможность зарабатывать деньги на политике. Заработанные деньги возможно вывести на любой электронный кошелек или банковскую карту. Как я проверил на личном опыте, все переводы проходят достаточно быстро. При желании на сайте можно не только выполнить ставку, но и следить за спортивным матчем онлайн. Плюсы букмекерской конторы Необходимо сразу же подметить, что эта контора обладает множеством несомненных достоинств: • Каждый день на ресурсе предоставляется большое количество спортивных событий, на которые возможно совершить ставки. • Ставки осуществляются в режиме реального времени. • Отличные коэффициенты. • Возможно выбрать любое предложенное киберспортивное состязание и выполнить на него ставку. • Быстрый вывод денег. Благодаря этим 1xbet скачать приложение преимущественным особенностям у меня получилось получить уже много денег. В случае если вам нужно 1xbet зеркало http://163.30.42.16/~health2017/userinfo.php?uid=2159397 – это именно то, что Вам требуется! Как можно пройти регистрацию в http://rewe.cc/wow/profile.php?mode=viewprofile&u=332695 Пройти регистрацию в данной букмекерской конторе не трудно. Попав на портал, возможно смело переходить к регистрации. Для этого необходимо вписать требуемые параметры, а после этого согласиться с условиями соглашения. Так, в учетной записи нет информации об игроке, и не нужно совершать верификацию. Человек получит 100 евро на свой счет в качестве начального бонуса. На портал БК можно попасть с помощью главной ссылки, но, к сожалению, ее часто блокируют. Поэтому стоит воспользоваться зеркалами или ТОР браузером для обхода блокировок. Благодаря зеркалу можно обойти блокировку, при этом изменяется только адрес сайта, сам же портал будет неизменным. Стоит отметить, что блокировка не говорит о том, что сайт является мошенническим. У букмекерской конторы имеются все лицензии, которые я самостоятельно проверил, когда регистрировался на ресурсе. Просто лицензии выданы не в Российской Федерации, из-за этого у нас в стране данный сайт блокируется. Лично я очень давно совершаю ставки в данной БК и пока ни разу не пожалел о том. Чаще всего я перехожу на сайт 1xbet через зеркало рабочее на сегодня прямо сейчас. В таком случае, я получаю ежедневный доступ на портал абсолютно всегда.

Posted on  13/11/2020 00:22:12  by  Cundiff
TMTX05 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 00:20:22  by  dobson
KqY7sJ 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:06:16  by  dobson
KYyvVg http://xnxx.in.net/ xnxx videos

Posted on  12/12/2020 20:30:11  by  johnan
H12CXb http://xnxx.in.net/ xnxx videos

Posted on  12/12/2020 21:37:51  by  johnan
6nqv3s https://writemyessayforme.web.fc2.com/

Posted on  13/12/2020 04:14:13  by  dobson
9ENCzt https://writemyessayforme.web.fc2.com/

Posted on  13/12/2020 05:51:35  by  dobson
AynKZs https://writemyessayforme.web.fc2.com/#writemyessay

Posted on  15/12/2020 05:14:22  by  dobson
IFmdcB https://writemyessayforme.web.fc2.com/#writemyessay

Posted on  15/12/2020 06:51:32  by  dobson
ncyCBB https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

Posted on  09/01/2021 09:46:50  by  dobson
VvhJy1 https://writemyessayforme.web.fc2.com/octavio-paz-essay-day-of-the-dead.html

Posted on  09/01/2021 12:10:48  by  dobson
jaiUTs http://waldorfdollshop.us/ waldorf doll

Posted on  09/01/2021 14:02:12  by  johnanz
sDB4LE http://waldorfdollshop.us/ waldorf doll

Posted on  09/01/2021 16:31:11  by  johnanz
PkOpQs https://beeg.x.fc2.com/

Posted on  26/01/2021 14:44:42  by  markus
BmjBKf https://beeg.x.fc2.com/

Posted on  26/01/2021 17:24:37  by  markus
gdBRjt https://buyzudena.web.fc2.com/

Posted on  27/01/2021 13:25:45  by  markus
dGp7Lm https://buyzudena.web.fc2.com/

Posted on  27/01/2021 14:39:25  by  markus
Leave a comment