Como provar que um idioma é regular?

Existem muitos métodos para provar que um idioma não é regular , mas o que preciso fazer para provar que um idioma é regular?

Por exemplo, se me é dado que é regular, como posso provar que o a seguir também é regular?$L$$L'$

$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$

Posso desenhar um autômato finito não determinístico para provar isso?

Sim, se você puder criar um dos seguintes:

• autômato finito determinístico (DFA),
• autômato finito não determinístico (AFN),
• expressão regular (regexp de linguagens formais) ou
• gramática regular

para alguma língua , então é regular. Existem modelos mais equivalentes , mas os itens acima são os mais comuns.$L$$L$

Também existem propriedades úteis fora do mundo "computacional". também é regular se$L$

• é finito,

• você pode construí-lo executando determinadas operações em idiomas regulares e essas operações são fechadas para idiomas regulares , como

  • interseção,
  • complemento,
  • homomorfismo,
  • reversão,
  • quociente esquerdo ou direito,
  • transdução regular

  e mais , ou

• usando o teorema de Myhill – Nerode se o número de classes de equivalência para for finito.$L$

No exemplo dado, temos alguns idiomas (regulares) como base e queremos dizer algo sobre uma linguagem derivada dele. Seguindo a primeira abordagem - construa um modelo adequado para - podemos assumir o modelo equivalente a que desejamos; permanecerá abstrato, é claro, já que é desconhecido. Na segunda abordagem, podemos usar diretamente e aplicar propriedades de fechamento para obter uma descrição para .L ′ L ′ L L L L $L$$L'$$L'$$L$$L$$L$$L'$

Métodos elementares

1. Autômatos finitos (possivelmente não determinísticos, com transições vazias).
2. Expressões regulares.
3. Equações lineares direita (ou esquerda, mas não ambas), como onde e são regulares.K $X = KX + L$$K$$L$
4. Gramática regular (tipo 3).
5. Operações que preservam linguagens regulares (operações booleanas, produto, estrela, shuffle, morfismos, inversas de morfismos, reversão etc.)
6. Reconhecido por um monóide finito.

Métodos lógicos (geralmente usados ​​na verificação formal)

1. Lógica monádica de segunda ordem (teorema de Büchi).
2. Lógica temporal linear (teorema de Kamp).
3. Teorema da árvore de Rabin (lógica monádica de segunda ordem com dois sucessores). Muito poderoso.

Métodos avançados

1. Lemas sofisticados de bombeamento. Veja, por exemplo,
   [1] J. Jaffe, um lema de bombeamento necessário e suficiente para idiomas regulares, Sigact News - SIGACT 10 (1978) 48-49.
   [2] A. Ehrenfeucht, R. Parikh e G. Rozenberg, Lemmas de bombeamento para conjuntos regulares, SIAM J. Comput. 10 (1981), 536-541.
   [3] S. Varricchio, Uma condição de bombeamento para conjuntos regulares, SIAM J. Comput. 26 (1997) 764-771.

2. Bem quase ordens. Ver
   [4] W. Bucher, A. Ehrenfeucht, D. Haussler, Sobre reguladores totais gerados por relações de derivação, Theor. Comput. Sci. 40 (1985) 131-148.
   [5] M. Kunz, soluções regulares de desigualdades de linguagem e quase-ordens de poço .

3. Suporte à série .$\mathbb{N}$

4. Métodos algébricos baseados em transduções (consulte também Operações preservando idiomas regulares ).

A resposta de Ran G. fornece uma lista bastante extensa dos modelos equivalentes que podem ser usados ​​para especificar idiomas regulares (e a lista continua, autômatos bidirecionais, lógica MSO, mas isso é coberto pelo link em 'modelos mais equivalentes '). E, como Raphael enfatiza, precisamos de um argumento para convencer o público de que a representação escolhida é realmente correta.

Reconsiderando a pergunta, ele adiciona 'Por exemplo '. Isso significa que precisamos fornecer uma construção válida que, considerando qualquer um dos modelos acima, assumimos que especifique a linguagem , transforme esse modelo em um para . Esse geralmente será o mesmo tipo de modelo, mas não precisa ser: podemos, por exemplo, começar com uma FSA determinística para e terminar com uma não determinística para .$\dots$$L$$L'$$L$$L'$

Isso inclui a possibilidade de usar operações de fechamento: na operação fornecida explicitamente no exemplo, temos .$L'= (\Sigma^* \setminus L) \cdot \Sigma^*$

Portanto, o que quero dizer é que a resposta é ótima, mas devemos adicionar a "construção de para ", quando não estiver construindo um idioma específico a partir do zero.$L$$L'$

Ocasionalmente, você encontrará um idioma especificado como "todas as cadeias de caracteres onde cada substring do elemento de satisfaz ", onde é alguma constante fixa. Nesse caso, o idioma será regular. A idéia aqui é definir um autômato finito em que alguns dos estados "lembram" os símbolos de entrada vistos mais recentemente , como na resposta a esta pergunta .$s$$k$$s$<some property>$k$$k$

Outro método, não coberto pelas respostas acima, é a transformação finita de autômatos . Como um exemplo simples, vamos mostrar que os idiomas regulares estão fechados na operação de reprodução aleatória , definida da seguinte forma: Você pode mostrar o fechamento em ordem aleatória usando as propriedades de fechamento, mas também pode mostrá-lo diretamente usando os DFAs. Suponha que seja um DFA que aceite (para ). Construímos um novo DFA seguinte maneira:

$$L_1 \mathop{S} L_2 = \{ x_1y_1 \ldots x_n y_n \in \Sigma^* : x_1 \ldots x_n \in L_1, y_1 \ldots y_n \in L_2 \}$$ $A_i = \langle \Sigma, Q_i, F_i, \delta_i, q_{0i} \rangle$$L_i$$i=1,2$$\langle \Sigma, Q, F, \delta, q_0 \rangle$

• O conjunto de estados é , onde o terceiro componente se lembra se o próximo símbolo é um (quando 1) ou (quando 2).$Q_1 \times Q_2 \times \{1,2\}$$x_i$$y_i$
• O estado inicial é .$q_0 = \langle q_{01}, q_{02}, 1 \rangle$
• Os estados de aceitação são .$F = F_1 \times F_2 \times \{1\}$
• A função de transição é definida por e .$\delta(\langle q_1, q_2, 1 \rangle, \sigma) = \langle \delta_1(q_1,\sigma), q_2, 2 \rangle$$\delta(\langle q_1, q_2, 2 \rangle, \sigma) = \langle q_1, \delta_2(q_2,\sigma), 1 \rangle$

---

Uma versão mais sofisticada desse método envolve adivinhação . Como exemplo, vamos mostrar que os idiomas regulares são fechados sob reversão , ou seja, (Aqui .) Essa é uma das operações de fechamento padrão, e o fechamento com reversão ocorre facilmente com a manipulação de expressões regulares (que pode ser considerada a contrapartida da transformação de autômatos finitos em expressões regulares) - apenas inverta a expressão regular. Mas você também pode provar o fechamento usando NFAs. Suponha que seja aceito por um DFA . Construímos um NFA

$$L^R = \{ w^R : w \in \Sigma^* \}.$$ $(w_1\ldots w_n)^R = w_n \ldots w_1$$L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$ , em que

• O conjunto de estados é .$Q' = Q \cup \{q'_0\}$
• O estado inicial é .$q'_0$
• O estado de aceitação exclusivo é .$q_0$
• A função de transição é definida da seguinte maneira: e para qualquer estado e , .$\delta'(q'_0,\epsilon) = F$$q \in Q$$\sigma \in \Sigma$$\delta(q', \sigma) = \{ q : \delta(q,\sigma) = q' \}$

(Podemos nos livrar de se permitirmos vários estados iniciais.) O componente de adivinhação aqui é o estado final da palavra após a reversão.$q'_0$

---

Adivinhar muitas vezes envolve também verificar. Um exemplo simples é o fechamento em rotação : Suponha que seja aceito pelo DFA . Construímos um NFA , que opera da seguinte maneira. O NFA adivinha primeiro . Em seguida, verifica se e que , movendo-se de para não determinística. Isso pode ser formalizado da seguinte maneira:

$$R(L) = \{ yx \in \Sigma^* : xy \in L \}.$$ $L$$\langle \Sigma, Q, F, \delta, q_0 \rangle$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$q=\delta(q_0,x)$$\delta(q,y) \in F$$\delta(q_0,x) = q$$y$$x$

• Os estados são . Além do estado inicial , os estados são , onde é o estado que adivinhámos, é o estado atual especifica se estamos em a parte da entrada (quando 1) ou na parte da entrada (quando 2).$Q' = \{q'_0\} \cup Q \times Q \times \{1,2\}$$q'_0$$\langle q,q_{curr}, s \rangle$$q$$q_{curr}$$s$$y$$x$
• Os estados finais são : aceitamos quando .$F' = \{\langle q,q,2 \rangle : q \in Q\}$$\delta(q_0,x)=q$
• As transições implementam a adivinhação .$\delta'(q'_0,\epsilon) = \{\langle q,q,1 \rangle : q \in Q\}$$q$
• As transições (para cada e ) simulam o DFA original.$\delta'(\langle q,q_{curr},s \rangle, \sigma) = \langle q,\delta(q_{curr},\sigma),s \rangle$$q,q_{curr} \in Q$$s \in \{1,2\}$
• As transições , para cada e , implementam o movimento da parte para a parte. Isso só é permitido se atingirmos um estado final na parte .$\delta'(\langle q,q_f,1 \rangle, \epsilon) = \langle q,q_0,2 \rangle$$q \in Q$$q_f \in F$$y$$x$$y$

---

Outra variante da técnica incorpora contadores limitados. Como exemplo, vamos considerar o fechamento da distância de edição de alteração : Dado um DFA para , e construa um NFA para do seguinte modo:

$$E_k(L) = \{ x \in \Sigma^* : \text{ there exists $y \in L$ whose edit distance from $x$ is at most $k$} \}.$$ $\langle \Sigma, Q, F, \delta, q_0 \rangle$$L$$\langle \Sigma, Q', F', \delta', q'_0 \rangle$$E_k(L)$

• O conjunto de estados é , em que o segundo item conta o número de alterações feitas até o momento.$Q' = Q \times \{0,\ldots,k\}$
• O estado inicial é .$q'_0 = \langle q_0,0 \rangle$
• Os estados de aceitação são .$F' = F \times \{0,\ldots,k\}$
• Para cada temos transições .$q,\sigma,i$$\langle \delta(q,\sigma), i \rangle \in \delta'(\langle q,i \rangle, \sigma)$
• As inserções são manipuladas pelas transições para todos os modo que .$\langle q,i+1 \rangle \in \delta'(\langle q,i \rangle, \sigma)$$q,\sigma,i$$i < k$
• As exclusões são manipuladas por transições para todos os modo que .$\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \epsilon)$$q,\sigma,i$$i < k$
• As substituições são identificadores semelhantes pelas transições para todos os tal que .$\langle \delta(q,\sigma), i+1 \rangle \in \delta'(\langle q,i \rangle, \tau)$$q,\sigma,\tau,i$$i < k$

Um idioma é regular se você puder escrever um scanner que decida sobre seqüências arbitrárias, se pertencem ou não ao idioma, usando não mais do que uma quantidade fixa de memória - ou seja, o reconhecimento pode ser feito no espaço O (1) .

A transformação de expressão regular é uma maneira de provar o fechamento em determinadas operações. Os dois exemplos mais simples são fechamento sob reversão e fechamento sob homomorfismo .

Dada uma expressão regular representando uma linguagem , podemos construir uma expressão regular para , a linguagem do verso de todas as palavras em , recursivamente:$r$$L$$L^R$$L$

• $\epsilon^R = \epsilon$ , , .$\sigma^R = \sigma$$\emptyset^R = \emptyset$
• $(r_1+r_2)^R = (r_1^R + r_2^R)$ , , .$(r^*)^R = (r^R)^*$$(r_1r_2)^R = r_2^R r_1^R$

Toda a ação acontece no final regra . Como exemplo, você pode verificar se . Estabelece indução estruturais que a linguagem da é, de fato . ( 0 ∗ 1 ∗ ) R = 1 ∗ 0 ∗ r R L $(r_1r_2)^R = r_2^R r_1^R$$(0^*1^*)^R = 1^*0^*$$r^R$$L^R$

Outro exemplo simples é o fechamento sob homomorfismo. Dado um homomorfismo e uma expressão regular para uma linguagem , podemos obter uma expressão regular para substituindo todas as instâncias de em por . r L h ( L ) σ r h ( σ $h\colon \Sigma \to \Delta^*$$r$$L$$h(L)$$\sigma$$r$$h(\sigma)$

Outra maneira é criar o idioma usando operações nas quais você sabe que eles estão fechados. Esta é uma extensão para exibir uma expressão regular, pois você tem muito mais operações disponíveis (inverter a corda, complemento, interseção, cortar um pedaço, apenas manter uma parte, homomorfismos e homomorfismos inversos, ...)