2001-gre-vs-practice.pdf/Q28 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
Илья52 (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
{{reserve-task|[[Участник:Илья52|илья52]] 11:02, 21 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Илья52|илья52]] 11:02, 21 декабря 2024 (UTC)}} | ||
| − | + | ||
| + | == Вопрос: Q28-e5724f == | ||
Ниже приведен конечный автомат, задающий регулярный язык <m>L</m>, <m>state0</m> - начальное и конечное состояние автомата. Какое регулярное выражение, из приведенных ниже, не задает подмножество языка <m>L</m>? | Ниже приведен конечный автомат, задающий регулярный язык <m>L</m>, <m>state0</m> - начальное и конечное состояние автомата. Какое регулярное выражение, из приведенных ниже, не задает подмножество языка <m>L</m>? | ||
| − | + | ||
<graph> | <graph> | ||
| Строка 21: | Строка 21: | ||
=== Ответы === | === Ответы === | ||
| − | + | * 0*(11)*0* | |
| − | + | * 0*1(10*1)*1 | |
| − | + | * 0*1(10*1)*10* | |
| − | + | * Правильный ответ: 0*1(10*1)0(100)* | |
| − | + | * (0*1(10*1)*10*+0*)* | |
| Строка 31: | Строка 31: | ||
=== Объяснение === | === Объяснение === | ||
| − | |||
{{cstest-source|2001-gre-vs-practice.pdf|25|28}} | {{cstest-source|2001-gre-vs-practice.pdf|25|28}} | ||
| − | Как можно заметить | + | Как можно заметить 0*1(10*1)0(100)* не подходит. После выполнения <m>0^{*}1(10^{*}1)0</m> автомат будет находиться в <m>state2</m>. Переход <m>(100)^{*}</m> соответствует переходу из <m>state2</m> в <m>state1</m> и обратно, т.е. в конце автомат будет в <m>state2</m>, но это не конечное состояние. |
| − | + | ||
| − | + | ||
| − | + | ||
{{question-ok|}} | {{question-ok|}} | ||
Версия 21:21, 23 декабря 2024
Задача зарезервирована: илья52 11:02, 21 декабря 2024 (UTC)
Вопрос: Q28-e5724f
Ниже приведен конечный автомат, задающий регулярный язык , - начальное и конечное состояние автомата. Какое регулярное выражение, из приведенных ниже, не задает подмножество языка ?
Ответы
- 0*(11)*0*
- 0*1(10*1)*1
- 0*1(10*1)*10*
- Правильный ответ: 0*1(10*1)0(100)*
- (0*1(10*1)*10*+0*)*
Объяснение
Исходники — вопрос 28 на 25 странице книги «2001-gre-vs-practice.pdf»
Как можно заметить 0*1(10*1)0(100)* не подходит. После выполнения автомат будет находиться в . Переход соответствует переходу из в и обратно, т.е. в конце автомат будет в , но это не конечное состояние.