Составители:
240
Детерминированные контекстно-свободные языки.
Проблемы соотношения между детерминированными контекстно-
свободными языками.
Даны языки L
1
и L
2
, принимаемые детерминированными магазинными
автоматами.
Вопросы:
1) L
1
∩ L
2
= ∅?
2) L
1
∩L
2
— контекстно-свободный язык?
3) L
1
∪L
2
— детерминированный?
4) L
1
⊆L
2
?
П.2. Разрешимые проблемы,
касающиеся детерминированных
контекстно-свободных языков
Некоторые вопросы, которые не разрешимы для контекстно-свободных
языков в общем случае, разрешимы для детерминированных языков.
Например, даны детерминированный контекстно-свободный язык L и
регулярное множество R. Разрешимы следующие вопросы:
1) L — существенно неоднозначен?
2) L = R?
3) L — регулярное множество?
4)
L = ∅?
5)
L
— контекстно-свободный язык?
6) L ⊇ R?
Неразрешённая проблема — неизвестно, разрешима или нет следующая
проблема.
Даны детерминированные магазинные автоматы M
1
и M
2
.
Вопрос: T(M
1
) = T(M
2
)?
Страницы
- « первая
- ‹ предыдущая
- …
- 239
- 240
- 241
- 242
- 243
- …
- следующая ›
- последняя »
