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