Expressoes LinguagensGramaticas Regulare

Teoria da Computação

Cap. 3 Expressões regulares, linguagens e gramáticas

CAPÍTULO 3

EXPRESSÕES REGULARES, LINGUAGENS REGULARES E
GRAMÁTICAS REGULARES

3.1 Introdução

117

3.2 Expressões Regulares

117

3.3 Regras algébricas para expressões regulares

126

3.4 Relação entre expressões regulares e linguagens regulares

130

3.5 Gramáticas regulares

140

3.6 Síntese das equivalências

151

LEI/DEI/FCTUC/2009/@ADC

Documento de trabalho

115

Teoria da Computação

LEI/DEI/FCTUC/2009/@ADC

Cap. 3 Expressões regulares, linguagens e gramáticas

Documento de trabalho

116

Teoria da Computação

Cap. 3 Expressões regulares, linguagens e gramáticas

3.1. Introdução
Vimos que uma linguagem é regular se for aceite por um DFA ou um NFA. Poderemos assim representar uma linguagem pelo seu autómato. Se o autómato tiver um elevado número de estados, não é possível, por simples inspecção visual, ver qual a sua linguagem. Interessa por isso uma forma mais simples de representar uma linguagem regular, que seja de utilização expedita, de modo análogo ao de uma fórmula química de uma substância: olhando para ela extrai-se logo uma grande quantidade de informação sobre a sua natureza.
É esse o objectivo das expressões regulares: são formas simples, expeditas, com muita informação, de representar linguagens regulares.
Mas se assim é, e se a uma expressão regular corresponde sempre uma linguagem regular, para uma expressão regular há-de haver um autómato finito que represente a mesma linguagem, dado que toda a linguagem regular tem o seu DFA ou NFA.
Há portanto uma estreita relação entre expressões regulares e linguagens regulares.
Estudá-la-emos neste capítulo.
Já vimos que uma linguagem pode ser definida por uma gramática. Dada uma linguagem regular, pode interessar conhecer uma gramática que a gere, e neste caso diz-se gramática regular. E é sempre possível encontrá-la, com recurso aos autómatos finitos.