пусть L = {wwRu | w, u ∈ {0,1}+}. Является ли L обычным языком? Обратите внимание, что w, u не может быть пустым.
Я пытался доказать, что это не обычный язык с помощью леммы о накачке, но потерпел неудачу, когда w = 0^p1^p, 01^p, (01)^p. Как только я возьму y = 0^p или 1^p, xyyz будет 00.../11.../01^n0... и т. д.
И я не могу нарисовать его DFA/NFA или написать его регулярное выражение, чтобы доказать, что это обычный язык.
Так L обычный или нет? Как я могу это доказать?
Язык не является регулярным, и мы можем доказать это с помощью теоремы Майхилла-Нероде.
Рассмотрим последовательность строк 01, 0101,..., (01)^n,...
Во-первых, обратите внимание, что ни одна из этих строк не находится на языке. Любой префикс любой из этих строк, который имеет четную длину, имеет форму (01) ^ 2m для некоторого m и, следовательно, просто более короткая строка в последовательности; при разделении такого префикса на две либо обе подстроки начинаются с 0 и заканчиваются на 1, либо первая подстрока начинается и заканчивается на 0, а вторая начинается и заканчивается на 1. В любом случае эти строки не имеют формы w(w^R)u для любого w или u.
Далее обратите внимание, что самая короткая возможная строка, которую мы можем добавить к любой из этих строк, чтобы создать строку в языке, всегда является обратной самой себе, за которой следует либо 0, либо 1. То есть, чтобы превратить 01 в строку в языке язык, мы должны добавить 100 или 101; нет более коротких строк, которые мы можем добавить к 01, чтобы получить строку на языке. То же самое верно и для 0101: 10100 и 10101 — это кратчайшие возможные строки, переводящие 0101 в строку в L. И так далее для каждой строки вида (01)^n.
Это означает, что каждая строка вида (01)^n различима относительно целевого языка w(w^R)u. Теорема Майхилла-Нероде говорит нам, что минимальный ДКА для регулярного языка имеет ровно столько состояний, сколько существует классов эквивалентности при отношении неразличимости. Поскольку у нас есть бесконечно много различимых строк относительно нашего языка, минимальный DFA для этого языка должен иметь бесконечно много состояний. Но DFA не может иметь бесконечно много состояний; это противоречие. Это означает, что наш язык не может быть регулярным.
Язык ОБЫЧНЫЙ:
L = 00(0+1)+ + 11(0+1)+ + 0(11)+0(0+1) + + 1(00)+1(0+1)+
(0101)(1010)1 по этому выражению будет исключено, хотя на самом деле принадлежит L…
- person Charles Zhang; 25.04.2021
