< /td>

EXPRESSÃO REGULAR
(ER)

linguagem--> linguagem regular --> expressão regular --> autômato finito deterministico		 É uma sequencia (conjunto) de simbolos e caracteres (classes) gerada por uma gramatica. É uma notação algebrica  alternativa para representar  a classe das linguagens regulares (linguagem do automata finito)  mais  restrita (simples) na hierarquia das gramaticas. Adequadas para comunicação humano x humano  e  humano x máquina
1.Finalidade Essa expressão é interpretada como uma regra, que indicará sucesso de uma entrada de dados . Surgiram como parte de um editor de texto para manipular dados.
  • Buscar um padrão de texto 
  • Validar um padrão de texto (analisador léxico) 
  • Mais recentemente sistemas de animação, hipertextos e hipermidias.

     
2.Contexto Pertence ao conjunto das  classes das linguagens regulares ( a mais restrita na hierarquia das gramaticas  segungo Chomsky) . Pascal , C, Java, etc são linguagens não regulares.
3.SintaxeÉ definida a partir de conjuntos (linguagens) básicos e operações de concatenação e de união

(? <identificador> <conteudo>
  • identificador - tipo de caracter
  • conteudo - o que será manipulado por esse caracter

    Ex.:     Usando uma ER literal:         er = /abc(?=yxz)/;        // pegue a string abc somente se ela for seguida por yxz
              Chamando a função construtor do objeto RegExp, como segue:    er = new RegExp("abc(?=yxz)");  
     
4.Elementos da expressão (Metacaracteres) 

      .    ?    *    +    ^    $    |    [ ]     { }     ( )    \
Estão dividos em 4 grupos:

Representantes
Metacaracter Nome Função
           .      Ponto um caracter q.q.
[.....] Lista Lista de caracteres permitidos
[^.....] Lista negada Lista de caracteres proibidos

Quantificadores
Metacaracter Nome Função
             ?     Opcional Zero ou um
* Asteristico Zer, um ou mais
+ Mais Um ou mais
{n,m} Chaves De n até m

Âncoras
Metacaracter Nome Função
             ^     Circunflexo Inicio da linha
$ cifrão Fim da linha
\b Borda Inicio ou fim de palavra

Outros
Metacaracter Nome Função
             \c     Escape Torna literal o caracter c
| Ou Ou um ou outro
(.....) Grupo Delimita um grupo
       \1.....\9 retrovisor Texto casado nos grupos 1...9

Obsrvação : Coringas usados nas linhas de comando não são expressões regulares. Ex.: *.txt  não é uma expressão regular. É um comando de linha.
5.Como se lê uma expressão Primeiro lê-se o átomo, depois entende-se o todo e depois se analisa as possibilidades.

6.Operadores Regular união (soma)   concatenação ou ponto (multiplicação)     fechamento ou estrela*  (reflexivo e transitivo)

As expressões regulares obedecem a muitas leis algébricas da aritmética. A união e a concatenação são associativas, mas só a união é comutatica . A concatenação se distribui sôbre a união( 0 +01* pode ser substituido por 01* ) . A união assim como a interseção é idempotente (2 expresões identicas podem ser susbstitidas por uma)

7.Precedencia dos operadores  .  Eliminação dos simbolos { e }, bem como U por simbolo + ou |.
   Ex.: A expressão (ab|c)* representa o conjunto {ε,ab,c,abc,cab,abab,cc,....)
 
Precedencia de operadores
Precedência Operador Representaçãoo
  Mais alta     Fechamento x* 
Intermediaria Concatenação x.y ou xy
Mais baixa União x|y ou x+ y
8.Expressões regulares e automatas finitosAutomatos finitos é um sistema de estados finitos e pré determinados. Pertencem  a classe de algoritimos mais eficientes (menor numero de redudancias de estado). Sistema de estados finitos  é um modelo matematico de sistema com entradas e saidas discretas. Cada estado resume somente as infromações do passado neccessários para determinar as ações para o proxima entrada. Ex,: Elevador - sistema que não memoriza as requisições anteriores. Cada estado sumariza as informações "andar corrente" e "direção de movimento". As entradas para o sistema são as requisições pendentes.

A construção de um sistema é, em geral, composicional, no sentido em que sistemas são construidos a partir de sistemas conhecidos,. Três formas de composição se destacam:
Sequencial: a execução da proxima componente depende da terminação da componente anterior. ex.: em uma fila o atendimento do proximo cliente depende do outro.
Concorrente: resulta em componentes independentes, podendo ser processado ao mesmo tempo.Ex.: diversos caixas  atendem independente,mente diversos clientes. Clientes nos caixas executam ações independente dos clientes que aguardam.
Não-determinista: A proxima componente a ser executada é uma escolha entre diversos componenets alternativos. O não determinismo pode ser:
    interno: o sistema escolhe aleatoriamente.
    externo: a escolha da proxima componente a ser executada é exetrna ao sistema. Ex. qdo dois ou mais caixas ficam livres e o cliente escolhe.

O automata finito pode ser:  deterministico (único estado bem determinado), não-deterministico (conjunto de estados alternativos) e com movimentos vazios (sem ler qq simbolo pode assumir um conjunto de estados. Podem ser vistos como transações encapsuladas, excetuando por eventual mudança de estado, analago a encapsulamento de linguagens orientadas a objeto).

O automato finito sempre para pois qq palavra é finita. Como um novo simbolo da entrada é lido a cada aplicação da função programa, não existe apossibilidadede ciclo infinito (loop).

Um linguagem L é dita uma linguagem regular po tipo 3 ,se existe pelo menos um autômato finito deterministico que aceta L.

Relacionamentos entre expressão regular (ER) e automata finito deterministico



9.Exemplo  .  Expressão Regular --> Linguagem regular     Se r é uma expressão regular , então GERA(r) é uma linguagem regular
 
Expressão regulares e correspondentes linguagens geradas
Expressão regular Linguagem Gerada
  aa    somente as palavras aa
ba* todas as palavras que iniciam por b, seguido por zero ou mais a
(a+b)* todas as palavras sobr {a,b}
10. ReferenciasExpressões regulares uma abordagem divertida. Aurelio Marinho Jargas. Novatec. 2ed. 2008
Linguagens formais. Teoria Modelagem e implementação. Marcus Vinicius Midena Ramos e outros. Bookman.. 2009
Linguagens formais e autômatos. Paulo Blauth Menezes. Bookman. 5ed. 2008
Introdução a teoria de autômatos, linguahens e computação. John E. Hopocroft e outros. Campus. 2ed. 2001