Existem várias maneiras de demonstrar que um idioma é regular. Aqui está um colapso dos métodos comuns, juntamente com explicações e exemplos:

1. Construindo um autômato finito (FA) ou autômato finito determinístico (DFA)

* Explicação: Se você pode construir um DFA ou NFA (autômato finito não determinístico) que aceita * tudo * e * apenas * as seqüências de caracteres no idioma, o idioma é regular.
* Como fazer:
* Defina os estados: Os estados da sua FA representam a "memória" do que foi visto até agora na sequência de entrada. Pense em quais informações são essenciais para lembrar para determinar se a string está no idioma.
* Defina as transições: As transições determinam como a FA se move de estado para estado com base nos símbolos de entrada. Verifique se suas transições refletem corretamente as regras do idioma.
* Defina o estado inicial: Onde o autômato começa a processamento.
* Defina os estados aceitadores: Os estados que indicam a sequência estão no idioma.
* Exemplo: Considere o idioma l ={strings sobre {a, b} que contêm "ab" como uma substring}.

`` `
Estados:Q0 (Start), Q1, Q2 (aceitação)

Transições:
- Q0, a -> Q1 (visto e 'a' até agora, potencialmente levando a "ab")
- Q0, B -> Q0 (visto A 'B', Redefinir)
- Q1, a -> Q1 (visto 'aa' até agora, ainda procurando "ab")
- Q1, B -> Q2 (Visto 'Ab'!)
- Q2, A -> Q2 (já visto 'Ab', então qualquer entrada mais importante nos mantém aceitando)
- Q2, B -> Q2 (já visto 'Ab', então qualquer entrada mais importante nos mantém aceitando)

Start State:Q0
Estado de aceitação:Q2
`` `

Você pode desenhar um diagrama de estado para visualizar esta FA.

2. Construindo uma expressão regular

* Explicação: Se você pode escrever uma expressão regular que descreva * tudo * e * apenas * as seqüências de caracteres no idioma, o idioma é regular.
* Como fazer:
* Entenda os operadores básicos de expressão regular:
* Concatenação:`ab` (corresponde à string" ab ")
* União (ou):`a | B` (corresponde a" a "ou" b ")
* Kleene Star (zero ou mais repetições):`a*` (corresponde "", "a", "aa", "aaa", ...)
* Kleene Plus (uma ou mais repetições):`a+` (corresponde a "a", "aa", "aaa", ...)
* Parênteses para o agrupamento:`(a | B) C` (corresponde" AC "ou" BC ")
* Classes de personagens:`[abc]` (corresponde 'a', 'b' ou 'c')
* Intervalos:`[a-z]` (corresponde a qualquer letra minúscula)
* Divida o idioma em partes menores e combine -as usando os operadores.
* Exemplo: Usando o mesmo idioma L ={strings sobre {a, b} que contêm "ab" como uma substring}.

A expressão regular é:`(a | b)*ab (a | b)*`

* `(a | b)*` significa zero ou mais ocorrências de 'a' ou 'b' (qualquer sequência de 'a's e' b's).
* `ab` é a substring necessária.
* `(a | b)*` novamente permite qualquer sequência de 'a's e' b's* depois* "ab".

3. Usando propriedades de fechamento de idiomas regulares

* Explicação: Os idiomas regulares são fechados sob determinadas operações. Isso significa que, se você aplicar essas operações a idiomas regulares, o resultado também será um idioma regular. As propriedades de fechamento comuns incluem:
* União
* Concatenação
* Kleene Star
* Interseção
* Complementação
* Diferença
* Reversão
* Homomorfismo (substituição)
* Como fazer:
1. Mostre que o idioma pode ser construído a partir de idiomas regulares mais simples e conhecidos usando operações de fechamento.
2. Por exemplo, se você pode mostrar que seu idioma é a união de dois idiomas regulares, você provou que é regular.
* Exemplo: Seja l1 ={strings sobre {a, b} começando com 'a'} e l2 ={strings sobre {a, b} terminando com 'b'}. L1 e L2 são regulares (você pode escrever facilmente expressões regulares para eles:`a (a | b)*` e `(a | b)*b`).

Agora, considere o idioma l =l1 ∩ l2 ={strings sobre {a, b} começando com 'a' * e * terminando com 'b'}.

Como os idiomas regulares são fechados sob interseção, L também é regular. Sua expressão regular é `a (a | b)*b`.

4. Teorema de Myhill-nerode

* Explicação: O teorema de Myhill-irode fornece uma condição necessária e suficiente para que um idioma seja regular. Ele afirma que um idioma l é regular se e somente se tiver um número finito de *sufixos distinguíveis *. Dois sufixos *x *e *y *são distinguíveis em relação a *l *se existir uma string *z *tal que exatamente um dos *xz *ou *yz *está em *l *. Em termos mais simples:um idioma L é regular se você puder dividir todos os prefixos possíveis em um número finito de classes de equivalência.
* Como fazer isso (mais avançado):
1. Defina uma relação de equivalência baseada em sufixos distinguíveis:`x ≡ y` se e somente se para todas as cordas` z`, `xz ∈ L` se e somente se` yz ∈ L`.
2. Mostre que o número de classes de equivalência sob essa relação é finito. Se for, o idioma é regular. O número de classes de equivalência é igual ao número de estados no DFA mínimo para o idioma.
* Exemplo: Seja L ={0 n 1 n | n ≥ 0}. Esta é uma linguagem * não regular * (usada para demonstrar o lema de bombeamento). Para entender intuitivamente o aplicativo Myhill-irode:

Considere os prefixos 0, 00, 000, .... se eu fosse regular, eventualmente dois prefixos, digamos 0 i e 0 j (onde eu eu para 0 i , você recebe 0 eu 1 i , que * está * em L. No entanto, se você anexar 1 i para 0 j , você recebe 0 j 1 i , que * não está * em l (porque j> i). Assim, 0 i e 0 j são distinguíveis. Como você pode criar um número infinito de prefixos distinguíveis, o idioma não é regular. O teorema de Myhill-irode é frequentemente usado para provar que um idioma * não é * regular.
5. O lema de bombeamento para idiomas regulares (para provar um idioma * não * regular)

* Explicação: O lema de bombeamento é uma ferramenta para provar que um idioma não é * regular. Ele afirma que se um idioma l é regular, existe um comprimento de bombeamento *p *(um número inteiro), de modo que qualquer string *s *em l com comprimento maior ou igual a *p *possa ser dividida em três substringas, *x *, *y *e *z *, onde *s *=*xyz *e as seguintes condições seguram:
1. Para cada i> =0, xy i Z está em L. (você pode "bombear" a parte y qualquer número de vezes e o resultado ainda está no idioma).
2. | Y |> 0. (A parte "bombeada" deve ter comprimento pelo menos 1).
3. | Xy | <=p. (A parte "bombeada" deve ocorrer dentro dos primeiros caracteres P).
* Como usá-lo para provar a não regularidade:
1. Suponha que L seja regular.
2. Suponha que o comprimento do bombeamento seja *p *. (Você não sabe o que é * P *, mas você assume que ele existe).
3. Escolha uma string * s * em l tal que | s |> =*p *. A chave aqui é escolher uma string * s * que levará a uma contradição mais tarde. Esta é geralmente a parte mais complicada.
4. considere todas as maneiras possíveis de dividir * s * em * xyz * tal que | y |> 0 e | xy | <=*p *.
5. Z* não é** em l. Isso contradiz o lema de bombeamento, que diz que * para todos * i, xy i Z deve estar em L.
6. Desde que você encontrou uma contradição, sua suposição inicial de que L é regular deve ser falsa. Portanto, L não é regular.
* Exemplo: Seja l ={a n B n | n> =0}. Prove que L não é regular.

1. Suponha que L seja regular.
2. Vamos * P * o comprimento do bombeamento.
3. escolha * s * =a p b p . Observe que | s | =2p> =p.
4. Considere as possíveis divisões de * s * em * xyz * com | y |> 0 e | xy | <=*p *. Desde | xy | <=* p * e * s * começa com um p , * xy * deve consistir apenas em 'A's. Portanto:
* x =a j para alguns j> =0
* y =a k para alguns k> 0 (porque | y |> 0)
* z =a p-j-k b p
5. escolha i =0. Então xy i z =xz =a j A p-j-k b p =a p-k b p . Desde k> 0, p - k p-k b p não está * em L.
6. contradição! O lema de bombeamento diz que, por tudo, xy eu Z deve estar em L. encontramos uma divisão e um valor de i para o qual não é.
7. portanto, l não é regular.

Considerações -chave e práticas recomendadas:

* Escolha o método certo: O melhor método depende do idioma.
* Para idiomas simples, a construção de um DFA/NFA ou expressão regular é frequentemente a mais fácil.
* Para idiomas construídos a partir de outros idiomas regulares usando operações padrão, use propriedades de fechamento.
*Para os idiomas suspeitos de serem *não regulares *, use o teorema do lema de bombeamento ou Myhill-irode.
* clareza e rigor: Ao provar que um idioma é regular, defina claramente sua expressão de autômato/regular e explique por que aceita * todas as seqüências * no idioma e * apenas * essas strings. Em outras palavras, prove as duas direções da implicação. Uma descrição vaga não é suficiente.
* Minimização: Se você construir um DFA, é útil (mas não é necessário) para minimizá -lo. Um DFA minimizado é único para um determinado idioma.
* Prática: Trabalhar em muitos exemplos é a melhor maneira de entender esses conceitos e desenvolver a intuição necessária para aplicá -los de maneira eficaz.

Em resumo, provar que um idioma é regular normalmente envolve demonstrar sua equivalência a uma definição formal de regularidade:construindo diretamente uma máquina (FA) ou padrão (expressão regular) que a reconhece, ou mostrando que ela é construída a partir de componentes regulares usando operações conhecidas que preservam a regularidade. O lema de bombeamento, por outro lado, é usado para refutar a regularidade.