Skip to content

notebook.org

Latest commit

 

History

History
428 lines (427 loc) · 17.5 KB

notebook.org

File metadata and controls

428 lines (427 loc) · 17.5 KB
Raw

Linguagens regulares

Alfabetos

Um alfabeto é denotado por $Σ$. Exemplos:

Palavras

Uma palavra (ou cadeia) é uma sequência de zero ou mais símbolos do alfabeto. @@latex:\[5pt]@@ Notação:

Concatenação:

Reverso:

Observação: uma palavra $w$ é um palíndromo se, e somente se $w\text{R} = w$.

Linguagens

Uma linguagem é um conjunto de palavras $L \subseteq Σ^*$. @@latex:\[5pt]@@ Operações:

Teorema: As linguagens regulares são fechadas sob as seguintes operações

  • União
  • Interseção
  • Complemento
  • Concatenação
  • Fecho de Kleene

Autômatos finitos

Determinísticos

Um autômato finito determinístico é definido por:

Notação:

Ainda, nos autômatos existe um estado especial, denonimado $∅$, que aprisiona todas as transições omitidas.

Computação

Seja $M = (Q,\, Σ,\, δ,\, q_0,\, F)$ um autômato finito determinístico, e $w ∈ Σ^*$.
Dizemos que $M$ aceita $w$ se existe uma sequência de estados $r_1, \,\hdots,\, r_n ∈ Q$ satisfazendo:

  1. $r_0 = q_0$
  2. $∀\, i ∈ [0, n): δ(r_i,\, wi + 1) = ri + 1$
  3. $r_n ∈ F$

Um autômato $M$ reconhece uma linguagem $L$ se $∀\, w ∈ L: M \text{ aceita } w$.
Uma linguagem é regular se existe um autômato finito que a reconhece.

Minimização de estados

Dois estados $e$ e $e’$ são equivalentes se

O algoritmo de minimização, então, é:

  1. Produza uma partição $P_0 = \{F,\, Q - F\}$ de $Q$, separando os estados finais dos não finais.
  2. Para cada bloco de estados $B$ na partição $P_i$, cada símbolo $s$ do alfabeto $Σ$, e cada par de estados ($e$, $e’$) contidos no bloco B: a. Sejam $d = δ(e, s)$ e $d’ = δ(e’ , s)$ os estados para os quais o AFD transita quando lê o sı́mbolo $s$ a partir dos estados $e$ e $e’$, respectivamente. b. Se $d$ e $d’$ pertencem a blocos diferentes na partiçãoo $P_i$, então os estados $e$ e $e’$ não são equivalentes, e devem ser separados na partição $Pi+1$.
  3. Se a partição $Pi+1$ for diferente da partiçãoo $P_i$, repita o passo 2.
  4. O autômato mínimo é construído de tal forma que seus estados são os blocos da última partição $P$ produzida.

Não determinísticos

Um autômato finito não determinístico é definido por:

Sendo $a ∈ Σ$ um símbolo, e $w ∈ Σ^*$ uma palavra, define-se a função de transição estendida:

Teorema: Todo AFN possui um AFD equivalente.
Por construção:

Transições $λ$

Um autômato finito não determinístico com transições $λ$ introduz a possibilidade de transições sem a consumação de símbolos.

Onde $Σλ = Σ ∪ \{λ\}$. @@latex:\[10pt]@@ Os estados para os quais se transita sem consumir símbolos é definido pelo fecho $λ$:

Teorema: O fecho lambda de um estado é pelo menos o próprio estado.

Assim, define-se a função de transição estendida:

Teorema: Todo AFN$λ$ possui um AFN equivalente.
Por construção:

Com pilha

Um autômato finito com pilha não determinístico é definido por:

Em cada transição, o elemento do topo da pilha é retirado para a função de transição, que por sua vez devolve uma sequência de elementos a serem empilhados, além do estado transitado. @@latex:\@@
Um AFPN aceita uma palavra se ao consumí-la, encerra-se em um estado final com a pilha vazia.

Expressões regulares

Uma expressão regular pode ser uma das seguintes formas, cada qual com a linguagem correspondente:

Operações:

Linguagens irregulares

Nas linguagens regulares, têm se o lema do bombardeamento:
Se $L$ é uma linguagem regular, então

O lema pode ser utilizado para provar que uma dada linguagem não é regular.

Linguagens livres de contexto

Uma linguagem livre de contexto é uma linguagem que pode ser denotada por uma gramática livre de contexto.

Gramáticas livres de contexto

Uma gramática livre de contexto é definida por:

  1. O lado esquerdo de uma regra é constituído por uma única variável.
  2. O lado direito é constituído por uma combinação de terminais e variáveis.

Por convenção a variável inicial é a variável alvo da primeira regra. @@latex:\vspace{5pt}@@
Exemplo:

Lema: Para toda GLC, existe um AFPN que a reconhece.

Lema: Para todo AFPN, existe uma GLC equivalente. @@latex:\newpage@@ Nas linguagens livres de contexto, têm se o lema do bombardeamento:
Se $L$ é uma linguagem livre de contexto, então

O lema pode ser utilizado para provar que uma dada linguagem não é livre de contexto.

Forma normal de Chomsky

Uma gramática livre de contexto está na forma normal de Chomsky se todas as suas regras de produção estão em uma das seguintes formas:

Onde apenas $A$ e $S$ podem ser a variável inicial. @@latex:\@@
Teorema: toda gramática livre de contexto pode ser transformada para a forma normal de Chomsky.

Propriedade de fechamento

A classe das linguagens livre de contexto são fechadas sob as seguintes operações

  • União
  • Concatenação
  • Fecho de Kleene

@@latex:\pagebreak@@

Máquinas de Turing

Uma máquina de Turing é definida por:

Esta máquina possui uma fita, que inicialmente é

A função de transição percorre a fita, consumindo símbolos e produzindo um estado alvo, o símbolo a substituir o símbolo atual, e a direção do próximo caminhamento. @@latex:\@@
O demarcador limita o caminhamento à esquerda, ao contrário do caminhamento à direita que é ilimitado:

A máquina aceita uma palavra caso a transição estendida sobre esta palavra encerra em um estado final. Ao contrário dos autômatos, a máquina não transita implicitamente para um estado de erro quando a transição é indefinida. Neste caso, a máquina encerra a execução no estado corrente.

Linguagens recursivas e recursivamente enumeráveis

Linguagens recursivamente enumeráveis são as linguagens reconhecidas por uma máquina de turing.
Linguagens recursivas são as linguagens reconhecidas por uma máquina de turing que sempre encerra. @@latex:\@@ \ Portanto, as linguagens recursivas são um subconjunto das linguagens recursivamente enumeráveis.

Gramáticas Irrestritas

Uma gramática irrestrita é dada por

As linguagens geradas por gramáticas irrestritas são linguages recursivamente enumeráveis.

Linguagens Sensíveis ao Contexto

Gramáticas Sensíveis ao Contexto

Uma gramática sensível ao contexto é dada por

As gramáticas sensíveis ao contexto são mais restritas que as gramáticas irrestritas.

Autômato linearmente limitado

Um autômato linearmente limitado é uma maquina de turing não determinística com uma fita limitada:

Esta máquina possui uma fita, que inicialmente é

Hierarquia de Chomsky

Chomsky definiu a seguinte hierarquia das linguagens:

Tese de Church-Turing: Se uma função é computável, ela pode ser computada pela máquina de Turing.