Математическая теория формальных языков - тест 16

Алгоритмические проблемы, связанные с контекстно-свободными языками

Язык может быть представлен

С помощью контекстно-свободной грамматики и автоматов с магазинной памятью 

Проблема пустоты пересечения контекстно-свободных языков

Проблема бесконечности пересечения контекстно-свободных языков

Проблемы пустоты и бесконечности пересечения контекстно-свободных языков

Проблема однозначности контекстно-свободной грамматики

Проблема равенства контекстно-свободных языков

Проблема автоматности контекстно-свободного языка

Проблема контекстной свободности дополнения контекстно-свободного языка

Проблема пересечения контекстно-свободных языков

Проблема контекстной свободности дополнения контекстно-свободного языка и пересечения контекстно-свободных языков

Язык, согласно определению

Алгоритм, позволяющий определить, является ли пустым множеством пересечение языков грамматик

Если постовская система соответствия имеет хотя бы одно решение, то

Алгоритм, позволяющий по произвольной контекстно-свободной грамматике узнать, является ли грамматика однозначной

Определить однозначность грамматики по произвольной контекстно-свободной грамматике

По произвольной контекстно-свободной грамматике

Грамматика является неоднозначной тогда и только тогда, когда

Если постовская система соответствия имеет решение, то грамматика является

Если постовская система соответствия не имеет решения, то грамматика

"Раскрытием" определенных вспомогательных символов можно получить

Линейную грамматику можно получить путем

Получение линейной грамматики посредством "раскрытия" определенных вспомогательных символов

Дополнение языка является непустым тогда и только тогда, когда постовская система соответствия

Дополнение языка является бесконечным тогда и только тогда, когда постовская система соответствия

Пересечение языков является непустым тогда и только тогда, когда постовская система соответствия