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

UptoLike

ВУЗ: 

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

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

Рубрика: 

239
Приложение
НЕРАЗРЕШИМЫЕ И РАЗРЕШИМЫЕ ПРОБЛЕМЫ,
КАСАЮЩИЕСЯ ФОРМАЛЬНЫХ ЯЗЫКОВ
Здесь мы перечислим без доказательств алгоритмически неразрешимые и
разрешимые проблемы, относящиеся к различным свойствам формальных
языков.
П.1. Неразрешимые проблемы
Контекстно-зависимые языки.
Проблема пустоты: дана контекстно-зависимая грамматика G. Вопрос:
L(G)=∅?
Контекстно-свободные языки.
Проблема
пустоты пересечения: даны произвольные контекстно-сво-
бодные
грамматики G
1
и G
2
. Вопрос: L(G
1
)∩L(G
2
)= ∅?
Проблема полноты: дана контекстно-свободная
грамматика G, словарь
терминалов которой есть Σ.
Вопрос: L(G)=Σ
*
?
Проблемы отношений между контекстно-свободными
языками и
регулярными множествами: даны контекстно-свободная грамматика G и
регулярное множество R. Вопросы:
1) L(G) = R?
2) L(G) ⊇ R?
3)
)(GL = ∅?
Проблемы
эквивалентности и вложенности: даны контекстно-
свободные
грамматики G
1
и G
2
. Вопросы:
1) L(G
1
) = L(G
2
)?
2) L(G
1
) ⊆ L(G
2
)?
Проблема принадлежности пересечения классу контекстно-
свободных языков: даны контекстно-свободные
грамматики G
1
и G
2
.
Вопрос: L(G
1
) ∩ L(G
2
) — контекстно-свободный язык?
Проблема принадлежности дополнения классу контекстно-
свободных языков: дана контекстно-свободная
грамматика G. Вопрос: )(GL
— контекстно-свободный язык?
Проблема регулярности языка: дана контекстно-свободная грамма-
тика
G. Вопрос: L(G) — регулярное множество?
Неоднозначность контекстно-свободных грамматик и языков.
Неоднозначность контекстно-свободных грамматик: дана произ-
вольная контекстно-свободная грамматика
G. Вопрос: G — однозначна?
Проблема существенной синтаксической неоднозначности кон-
текстно-свободных языков: дана произвольная контекстно-свободная
грамматика G. Вопрос: L(G) — существенно однозначен?

Страницы