Если pref(L) регулярна, означает ли это, что L также регулярна?

У меня есть это упражнение для домашнего задания:

Скажем, у нас есть язык L. Мы знаем, что язык pref(L) (все префиксы L, включая все слова в самом L) является обычным языком. Означает ли это, что язык L также является регулярным?

Я взял NFA pref(L) и разделил его (через 2 эпсилон-перехода от q0) на 2 отдельных NFA, так как 1 определяет L, а другой определяет pref(L)\L.

На самом деле я получил NFA для L, что означает, что он обычный.

Я не уверен, что это правильно и законно ли это. Буду рад еще одной зацепке.

Заранее спасибо,

Ярон.


dfa regular-language automaton nfa
person user76508    schedule 24.11.2014    source источник
comment
Этот вопрос кажется не по теме, потому что он касается общей информатики, а не практического программирования. Попробуйте cs.stackexchange.com.   -  person Barmar    schedule 24.11.2014

Ответы (1)


arrow_upward
2
arrow_downward

Не обязательно, что если pref(L) регулярна, то и L регулярна.

Например, пусть = {a} — унарный алфавит. Я собираюсь утверждать, что если L — это любой бесконечный язык над , то pref(L) = *. Чтобы убедиться в этом, сначала обратите внимание, что pref(L) *, потому что каждый pref(L) является языком над . Теперь рассмотрим любую строку в *, которая должна иметь форму n. Если L — бесконечный язык над , он должен содержать хотя бы одну строку вида am, где m n. Тогда an будет префиксом am, поэтому an pref(L). Это показывает, что * pref(L) и что pref(L) *, так что в данном случае * = pref(L).

Теперь все, что нам нужно сделать, это найти нерегулярный язык над = {a}. В качестве примера возьмем язык { a2n | n N } всех строк, длина которых равна степени двойки. Используя теорему Майхилла-Нероде или лемму о накачке, можно доказать, что этот язык не является регулярным. Однако из приведенного выше результата мы знаем, что pref(L) — регулярный язык.

Надеюсь это поможет!

person templatetypedef    schedule 29.12.2014