2011-gre-cs-practice-book.pdf/Q04 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q04-08c765 == | == Вопрос: Q04-08c765 == | ||
| − | + | <graph> | |
| − | [[ | + | digraph G{ |
| + | rankdir=LR; | ||
| + | edge [color=blue]; | ||
| + | S -> T [label="x"] | ||
| + | T -> T [label="x"] | ||
| + | T -> U [label="x"] | ||
| + | T -> U [label="y"] | ||
| + | U -> U [label="y"] | ||
| + | U -> V [label="x"] | ||
| + | V [shape=doublecircle] | ||
| + | } | ||
| + | </graph> | ||
Что из следующего является регулярным выражением, соответствующим автомату выше? | Что из следующего является регулярным выражением, соответствующим автомату выше? | ||
=== Ответы === | === Ответы === | ||
| − | + | * <m>xxx+yyx</m> | |
| − | + | * <m>x^3y^2x</m> | |
| − | + | * <m>x^*y^*x</m> | |
| − | + | * Правильный ответ: <m>xx^*(x+y)y^*x</m> | |
| − | + | * <m>x^*xy^*x</m> | |
=== Объяснение === | === Объяснение === | ||
{{cstest-source|2011-gre-cs-practice-book.pdf|16|4}} | {{cstest-source|2011-gre-cs-practice-book.pdf|16|4}} | ||
| − | |||
| − | Пояснение: под + подразумевается объединение, в интернете беда с толковыми источниками | + | Очевидно, что следуя переходам между состояниями автомата мы получим вариант <m>xx^*(x+y)y^*x</m>. |
| + | |||
| + | Пояснение: под + подразумевается объединение, в интернете беда с толковыми источниками. | ||
| + | |||
| + | {{question-ok|[[Участник:StasFomin|StasFomin]] 15:16, 19 декабря 2024 (UTC)}} | ||
| − | + | [[Категория:Формальные языки]] | |
| − | + | ||
Текущая версия на 15:18, 19 декабря 2024
Вопрос: Q04-08c765
Что из следующего является регулярным выражением, соответствующим автомату выше?
Ответы
- Правильный ответ:
Объяснение
Исходники — вопрос 4 на 16 странице книги «2011-gre-cs-practice-book.pdf»
Очевидно, что следуя переходам между состояниями автомата мы получим вариант .
Пояснение: под + подразумевается объединение, в интернете беда с толковыми источниками.