Ok, vamos explorar idiomas regulares com exemplos e suas definições na teoria formal da linguagem.

O que são idiomas regulares?

No domínio da teoria da linguagem formal, um idioma regular é um idioma (um conjunto de cordas sobre um determinado alfabeto) que pode ser descrito por:

* Expressões regulares: Um padrão que define um conjunto de cordas.
* Autômatos finitos determinísticos (DFA): Uma máquina que lê a entrada de um símbolo de cada vez e faz transições entre os estados com base na entrada. Ele aceita ou rejeita a entrada com base no estado final.
* Autômatos finitos não determinísticos (NFA): Semelhante ao DFAS, mas permita várias transições possíveis de um estado para um determinado símbolo de entrada (ou até mesmo transições sem ler nenhuma entrada).
* gramáticas regulares: Um tipo de gramática formal, onde as regras de produção têm um formulário específico.

Essas quatro representações são equivalentes. Se você pode definir um idioma com um deles, poderá defini -lo com todos eles. Este é um teorema fundamental na teoria formal da linguagem.

Exemplos de idiomas regulares

Aqui estão alguns exemplos, além de como eles podem ser definidos usando os métodos mencionados acima:

1. a linguagem de todas as cordas sobre {0, 1} que começam com um '1'.

* Expressão regular: `1 (0 | 1)*` (ou `1 [01]*`)
* `1` corresponde ao necessário '1' no início.
* `(0 | 1)` significa "0 ou 1".
* `*` significa "zero ou mais ocorrências do grupo anterior".
* dfa:

`` `
0 1
-> Q0 Q1 Q1 (Q0 é o estado de partida)
Q1 Q1 Q1 (Q1 é um estado de aceitação)
`` `
* `q0` é o estado inicial. Se a entrada começar com '1', ela transita para o estado aceitável `q1`. Se começar com `0`, ele se moverá para o estado não aceitável (morto).
* `q1` é o estado de aceitação. Quando atinge esse estado, ele permanece nele, aceitando qualquer entrada adicional.
* NFA: Um NFA pode ser construído da mesma forma, mas pode ter um caminho alternativo a partir do estado inicial.
* Gramática regular: (Linear direito)

`` `
S -> 1A
A -> 0A | 1a | ε
`` `

* `S` é o símbolo inicial.
* `A` gera qualquer combinação de 0s e 1s, incluindo a corda vazia (ε).

2. a linguagem de todas as cordas sobre {a, b} que contêm a substring "ABA".

* Expressão regular: `(a | b)*aba (a | b)*` (ou `[ab]*aba [ab]*`)
* `(a | b)*` corresponde a qualquer sequência de 'A e' B's (zero ou mais).
* `ABA` corresponde à substring necessária.
* dfa: Este DFA terá estados para acompanhar o progresso da correspondência "ABA":

`` `
a b
-> Q0 Q1 Q0
Q1 Q1 Q2
Q2 Q1 Q0
Q3 Q3 Q3 (Q3 é um estado de aceitação)
`` `

* `q0`:estado inicial. Representa que não vimos nenhuma parte de "Aba".
* `Q1`:representa que vimos" A ".
* `Q2`:representa que vimos" ab ".
* `q3`:representa que vimos" Aba "(aceitando o estado). Uma vez em `q3`, qualquer entrada adicional o mantém em` q3`.
* NFA: Um NFA pode ser mais simples de construir para esse idioma. Pode "adivinhar" quando a substring "ABA" pode começar.
* Gramática regular:

`` `
S -> AS | BS | aa
A -> bb
B -> AC
C -> AC | BC | ε
`` `

3. a linguagem de todas as cordas sobre {0, 1} com um número par de 0s.

* Expressão regular: `1*(01*01*)*`
* `1*`:zero ou mais
*`01*01*`:Isso significa que a string deve ter um número par de 0s, pois qualquer 0 deve ser seguido por `1*01*`, para que seja emparelhado.
* dfa:

`` `
0 1
-> Q0 Q1 Q0 (Q0 é o estado de partida e aceitação)
Q1 Q0 Q1 (Q1 é um estado não aceitável)
`` `

* `Q0`:Número de 0s (estado de início e aceitação).
* `Q1`:número ímpar de 0s.
* NFA: Um NFA pode ser construído, mas o DFA é frequentemente a representação mais direta.
* Gramática regular:

`` `
S -> 1S | 0a | ε
A -> 1A | 0s
`` `

4. o idioma que consiste apenas na string "hello".

* Expressão regular: `Olá`
* dfa:

`` `
olá
-> Q0 Q1 - - - - (Q0 é o estado inicial)
Q1 - Q2 - - - -
Q2 - - Q3 - - -
Q3 - - - Q4 -
Q4 - - - - Q5
Q5 - - - - - (Q5 é um estado de aceitação)
`` `
* Gramática regular:

`` `
S -> ha
A -> eb
B -> LC
C -> LD
D -> O.
`` `

Exemplos de idiomas que não são regulares

Esses idiomas * não podem * ser representados por expressões regulares, DFAs, NFAs ou gramáticas regulares. Eles exigem formalismos mais poderosos, como gramáticas sem contexto ou máquinas de Turing.

1. A linguagem das cordas com um número igual de 'A e' B's: {ε, ab, ba, aabb, abab, baba, bbaa, ...}
2. A linguagem dos palíndromos (strings que lêem os mesmos para frente e para trás):{ε, a, b, aa, bb, aba, bab, abba, ...}
3. a linguagem {a n B n | n> =0} :Strings com `n` 'A são seguidos por` n`' b's (por exemplo, ε, ab, aabb, aaabbb, ...). Este é um exemplo clássico frequentemente usado para demonstrar as limitações dos idiomas regulares.
4. a linguagem {a n b m c n | n, m> =0} :Strings com `n` A's, seguidos por` m` b's e `n` c's. Isso não é regular.

Por que esses idiomas não são regulares?

A principal limitação dos idiomas regulares é a incapacidade de "contar" ou "lembrar" uma quantidade arbitrária de informações. Um DFA, NFA ou expressão regular tem um número finito de estados ou símbolos. Para reconhecer idiomas como {a n B n }, você precisaria acompanhar o número de 'A que você viu para garantir que haja o mesmo número de' B. Um autômato finito não possui a capacidade de memória de fazer isso para arbitrariamente grande `n`. Essa intuição é formalizada pelo *Lema de bombeamento para idiomas regulares *, uma ferramenta poderosa para provar que um idioma não é *regular.

em resumo

Os idiomas regulares são uma classe fundamental de idiomas na teoria formal da linguagem. Eles são simples de definir e implementar, tornando -os úteis para muitas aplicações práticas (por exemplo, análise lexical em compiladores, correspondência de padrões nos editores de texto, roteamento de rede). No entanto, eles têm limitações e idiomas mais complexos exigem formalismos mais poderosos.