Tribo do C.I.

Só mais um blog de informática (só que não)

Linguagens formais e Autômatos – 3

dezembro 1st, 2010

Para ver a segunda parte clique aqui

Expressões regulares – Toda Linguagem Regular pode ser descrita por uma expressão simples denominada Expressão Regular. Trata-se de um formalismo denotacional também considerado gerador, pois pode-se inferir como construir (“gerar”) as palavras de uma linguagem. É uma maneira de representar uma linguagem formada pela justaposição dos símbolos do alfabeto separados pelos símbolos de união ou concatenação.

Linguagem – Conjunto de palavras

L1 = {0,01,11} ou L2 = {111,000}

Operações

L1UL2 = {0,01,11,111,000}

L1L2 = {0111,0000,0011,…}

L1*={0000,010101,…)

Linguagens Regulares – São aquelas que podem ser representadas por expressão regular ou autômatos.

Exemplos:

  • L=Cadeias que possuem apenas um 0 E={0,1}
    • 1*01*
  • L=Cadeias que possuem todas as strings binárias E={0,1}
    • (0U1)*
  • L=Cadeias que possuem todas as strings binárias exceto o vazio E={0,1}
    • (oU1)+
  • L=Cadeias que começam com aa e terminam com bb E={a,b}
    • aa(aUb)*bb
  • L=Cadeias que começam ou terminam com bb E={a,b}
    • bb(aUb)*U(aUb)*bb

Por definição, uma linguagem é Regular se, e somente se, é possivel construir um Autômato Finito (Determinístico, Não-Determinístico ou com Movimentos Vazios), que reconheça a linguagem.

Transformação de Autômato/ER

  1. Incluir dois estados ( um inicial, que aponta para o inicial antigo por E(movimento vazio), e um estado final, todos os finais antigos do autômato deixam de ser finais e apontam por E para o novo).
  2. Avaliar dois a dois os estados na tentativa de eliminar um terceiro.


Hierarquia de Chomsky

É a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis (Descritos na figura ao lado), sendo que os dois últimos níveis (os níveis 2 e 3) são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. Mais especificamente, o nível 2 é utilizado em análise sintática (computação) e o nível 3 em análise léxica.

A classificação das gramáticas começa pelo tipo 0, com maior nível de liberdade em suas regras, e aumentam as restrições até o tipo 3. Cada nível é um super conjunto do próximo. Logo, uma gramática de tipo n é conseqüentemente uma linguagem de tipo n-1.

  • Linguagem tipo 3: Regular
    • Reconhecida por um autômato finito
    • Representada por uma expressão regular
  • Linguagem tipo 2: Livre de contexto
    • Reconhecida por um autômato de pilha
  • Linguagem tipo 1: sensível ao contexto
  • Linguagem tipo 0: Irrestrita
    • Máquina de Turing

Lema do Bombeamento

Diz que se pegarmos uma cadeia de tamanho maior do que a quantidade de estados do autômato, existe um pedaço dessa cadeia que pode ser bombeada (repetida em um looping) de forma que a cadeia gerada ainda pertence a linguagem.

Isso significa que existe um looping dentro do autômato. O lema do Bombeamento serve para provar que uma linguagem “NÃO” é regular. A demonstração de que uma linguagem é regular é feita através da criação de um autômato ou expressão regular.

Não é regular

-Afirme que é regular

-Escolha uma que você ache que não é regular

-Bombear

-Provar que não é regular.

O que foi descrito neste artigo é somente o começo dos estudos das linguagens formais. Foi dividido em 3 partes, é possível acessar a segunda parte clicando aqui, e a primeira parte clicando aqui. O artigo foi baseado no livro: Linguagens Formais e Autômatos, Série Livros Didáticos Segunda edição, de Paulo Fernando Blauth Menezes, com alguns pedaços de texto retirados da Wikipedia.


Expressões Regulares e suas respectivas linguagens

Expressão Regular

Linguagem Representada

aa

Somente a palavra aa

ba*

Todas as palavras que iniciam por b, seguido por zero ou mais a

(a+b)*

Todas as palavras sobre {a,b}

(a+b)*aa(a+b)*

Todas as palavras contendo aa como subpalavra

a*ba*ba*

Todas as palavras contend exatamente dois b

(a+b)*(aa+bb)

Todas as palavras que terminam com aa ou bb

(a+E)(b+ba)*

Todas as palavras que não possuem dois a consecutivos.

Sobre Sheldon Led:
Desenvolvedor e palestrante desde 2009. Já trabalhou com sistemas legados e software de gestão, mas hoje atua somente com web. Já participou do desenvolvimento de alguns portais governamentais e sites utilizando a plataforma Joomla e WordPress. Apesar de ser um desenvolvedor full-stack, tem focado seus estudos em tecnologias front-end e busca apoiar e colaborar em projetos envolvendo Software Livre, seja em eventos, material para estudo ou contribuição de código.

Tribo do C.I.

Tribo do C.I.

Só mais um blog de informática (só que não)