Show $ l= $ {w $ \ em (a, b) ^ * $ |Para cada substrição u de W, $ -5 \ le | u | _a- | u | _b \ le5} $ é regular

Question

Eu tento mostrar que esta linguagem é regular:

$ l= $ {w $ \ in \ (a, b) ^ * $ |Para cada subsfrições U de W, $ - 5 \ le | u | _a- | u | _b \ le5} $

Se eu construir um NFA e corro a cada substring de W (pule outras letras toda vez) - e somente se forem aceitos (segue a condição), aceite w. É possível no NFA?Existe outra maneira de mostrar a regularidade da linguagem?

Answer 1

Nice pergunta! Este é um problema muito intrometido envolvendo idiomas regulares.

Primeiro de tudo: Não, você não pode executar um autômato em cada substring de uma string pulando outras letras, você deve executar o autômato apenas uma vez na string de destino.

Neste caso, é mais simples raciocinar o complementares da linguagem dada, nomeadamente em

$$ l ^ c= {w \ in (a, b) ^ * \ mid \ text {há uma substring} u \ text {de} w \ text {tal que} | u | _a- | u | _b> 5 \ text {ou} | u | _a- | u | _b <-5} $$

A linguagem $ l ^ c $ é regular, pois é reconhecido pelo seguinte NFA:

(Cada nome do estado é a diferença $ | u | _a- | u | _b $ , a primeira letra da substring $ u $ é" encontrado "nondeterministicamente pelo NFA).

Então, como $ l ^ c $ é regular, também $ l= (l ^ c) ^ c) é.

---

.

Após a sugestão de Hendrick, tentei determinar o NFA e desenhar seu complemento, e recebo este bom DFA que reconhece $ l $ :

Cada nome de um nome de estado de aceitação é um intervalo: quando, executando o autômato, estamos em estado $ [x_1, x_2] $ e nós lemos o string $ z $ Isso significa que para todos $ x \ in [x_1, x_2] $ há um sufixo $ u $ de $ z $ tal que $ | u | _a- | u | _b= x $ . Caso contrário, disse, seguindo a sugestão de Dmitry, o autômato calcular o conjunto residual de $ z $ .

Em certo sentido, como Hendrick diz, é como se estivéssemos correndo o autômato em cada substring, mas isso não significa que possamos usar diretamente um DFA que reconheça strings de modo que a diferença entre a matemática $ a $ s e a $ b $ s está em $ [- 5,5 ] $ (que seria fácil de perceber) e executar este autômato em cada substring de um dado, e dessa maneira provar que a linguagem é regular.

---

.

Por fim, escreveria uma generalização trivial do resultado (acho que isso é folclore, mas não consegui encontrar uma referência).

Deixe $ t $ ser uma linguagem regular em um alfabeto $ \ sigma $ e deixe $ l $ Seja o idioma definido da seguinte forma:

$$ l= {w \ in \ sigma ^ * \ mid \ text {para cada substring} u \ text {de} w, \ u \ in t \} $$

Então, também $ l $ é regular.

De fato, como acima, considere $ l ^ c $ , o complemento de $ l $ , ou seja,

$$ l ^ c= {w \ in \ sigma ^ * \ mid \ text {há uma substring} u \ text {de} w \ text {tal que } u \ não \ in t \} $$

então $ l ^ c=sigma ^ * t ^ sigma ^ * t ^ sigma ^ * $ , e, portanto, $ l= (\ Sigma ^ * t ^ c \ sigma ^ *) ^ c $ é regular, pois a família de línguas regulares é encerrada sob concatenação e complementação.

Cleary O resultado ainda é verdadeiro para cada família de línguas fechadas sob concatenação e complementação, mas esta não é uma condição necessária. De fato, a família de línguas finitas não é fechada sob complementação, mas claramente se $ t $ é finito, então também $ L $ é (como é sempre o caso que $ l \ subseteq t $ ). Por outro lado, isso não é verdade para todas as classes de idiomas. Considere a família NR de idiomas não regulares, então $ t={1 ^ p \ meados p \ text {é prime}} \ in \ $ nr, Mas neste caso temos $ l=varnothing $ , que é regular.