Языки и трансляции. Мартыненко Б.К. - 46 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

45
Упражнения
I-3.1. Дан недетернинированный конечный автомат
M = ({q
0
, q
1
, q
2
}, {a, b}, δ, q
0
, {q
2
}), где
δ(q
0
, a) = {q
1
, q
2
}, δ(q
1
, a) = {q
0
, q
1
}, δ(q
2
, a) = {q
0
, q
2
},
δ(q
0
, b) = {q
0
}, δ(q
1
, b) = ϕ, δ(q
2
, a) = {q
1
}.
Построить детерминированный конечный автомат, эквивалентый данному fa M.
I-3.2. Построить конечный автомат по автоматной грамматике, порож-
дающей числа без знака языка Паскаль (см. упр. I-2.5).
I-3.3. Построить детерминированный конечный автомат, эквивалентный
недетерминированному автомату, построенному в упр. I-3.2.
I-3.4. По детерминированному конечному автомату, построенному в задаче
I-3.3, построить эквивалентную автоматную грамматику.
I-3.5. По автоматной грамматике, полученной в упр. I-3.4 построить
регулярное эквивалентное выражение.
I-3.6. Определите, является ли dfa M, построенный в упр. I-3.3,
минимальным.
I-3.7. По детерминированному конечному автомату из упр. I-3.3 построить
эквивалентную грамматику типа 3.
I-3.8. Доказать, что если L ⊆ Σ
*
— регулярное множество, то L
R
= {w
R
| w ∈
L} — тоже регулярное множество.
I-3.9. Пусть G = (V
N
, V
T
, P, S) — грамматика, каждое правило которой имеет
вид A → a или A → Ba, где A, B ∈ V
N
, a ∈ V
T
. Доказать, что L = L(G) — rs.
I-3.10. Пусть L ⊆ Σ
*
— rs. Доказать, что L
1
= {x | xy ∈ L} — rs.
I-3.11. Построить fa, распознающий язык L
1
из упр. I-3.10.
I-3.12. Построить fa, распознающий язык L = {w | w ∈ {0, 1}
*
}
и w не содер-
жит двух последовательных единиц}.
I-3.13. Построить регулярную грамматику по конечному автомату,
полученному в задаче I-3.12.
I-3.14. Пусть G — грамматика, в которой все правила имеют вид:
A → xB и A → x, где A и B — нетерминалы, а x — не пустая терминальная
цепочка. Покажите, что L(G) может быть порождён регулярной грамматикой.

Страницы