Linguagens e Expressões Regulares

Uma forma de especificar linguagens formalmente.

Na secção anterior observou-se que para definir uma linguagem de programação o fecho, $\cl{\Sigma}$, não é adequado porque tem “demasiadas” palavras.

Mais precisamente, a situação é a seguinte:

Para definir uma linguagem de programação começa-se for escolher um certo alfabeto e, sobre esse alfabeto, define-se uma linguagem cujas palavras são exatamente os programas válidos da linguagem de programação.

O Problema Principal de ALP (versão 0) – Dada uma linguagem $A$ e uma palavra $p$ no mesmo alfabeto, determinar se $p \in A$ – não desenvolve condições para determinar $p \in A$. É necessário um “sistema” que permita definir linguagens formais e que seja:

Computável: Existe um algoritmo que recebe como entrada uma palavra $p$ e ao fim de um número finito de passos produz uma resposta sim ou não conforme $p \in A$ ou não.
Eficiente: O número de passos referido no passo anterior não deve ser “muito maior” que o comprimento da palavra.
Adequado: Deve ser possível definir (os programas de) qualquer linguagem de programação.

Portanto:

Problema Principal de ALP (versão 1): Determinar um sistema computável e eficiente para determinar se $p \in A$ e que seja adequado (i.e., $A$ é uma linguagem de programação).

Linguagens Regulares

As operações entre linguagens (principalmente, a união, a concatenação e o fecho) permitem começar por linguagens muito simples e definir formalmente, rigorosamente, sem ambiguidades, linguagens mais complexas. Por exemplo, a partir do alfabeto binário $\set{\tt 0, 1}$, a linguagem das palavras com um número par de $\tt 1$ é $\cl{\set{\tt 0, 11}}$.

O ênfase em “formal, rigoroso, não ambíguo” é necessário para resolver algoritmicamente o Problema Principal de ALP. Mais especificamente, pretende-se obter um programa que tem como entrada uma especificação formal de uma linguagem e que produz um segundo programa que tem como entrada uma palavra e que determina se essa palavra pertence, ou não, à linguagem dada ao primeiro programa. Isto é, pretende-se definir um programa Super tal que

Se e for uma especificação formal de uma linguagem de programação L: PL = Super(e).
Seja p uma palavra. PL(p) é verdade ou falso conforme p in L ou não.
Tanto Super quanto PL devem ser eficientes.

O Problema Principal de ALP, nas suas várias versões, trata de encontrar uma “especificação formal” adequada e obter os programas Super e PL. De facto, a resolução seguida em ALP até vai mais longe: A resposta a $p \in A$ é calculada de forma que quando $p$ for um programa válido (isto é, “$p \in A$” é verdade) também se obtém uma “representação intermédia” de $p$, apta a ser executada.

Por enquanto define-se a classe das linguagens regulares:

Linguagem Regular (LR). Seja $\Sigma$ um alfabeto. Uma linguagem regular sobre $\Sigma$ define-se recursivamente pelas seguintes regras:

base Os conjuntos $\empty, \set{\nil}$ e, para cada $a \in \Sigma,\ \set{a}$ são linguagens regulares.

passo Se $A$ e $B$ forem linguagens regulares então $A\cup B, AB, \cl{A}$ também são linguagens regulares.

fecho Um conjunto de palavras é uma linguagem regular se, e só se, pode ser definido através de um número finito de aplicações do passo a partir dos conjuntos da base.

Alguns exemplos de linguagens regulares:

$\set{\tt 001, 110} = \set{\tt 0}\set{\tt 0}\set{\tt 1} \cup \set{\tt 1}\set{\tt 1}\set{\tt 0}$.
Qualquer linguagem finita.
O conjunto das palavras que começam em $\tt 0$ é infinito mas regular: $\set{\tt 0}\cl{\set{\tt 0, 1}}$.

Expressões Regulares

A notação usual dos conjuntos, com $\set{}, \del{}$, etc. torna difícil escrever e ler linguagens regulares. Para aliviar esse problema usa-se uma notação específica.

Expressão Regular (ER). Seja $\Sigma$ um alfabeto. Uma expressão regular sobre $\Sigma$ define-se recursivamente pelas seguintes regras:

base As expressões vazio $\empty$, palavra vazia $\nil$ e, para cada $a \in \Sigma,\ a$ são expressões regulares.

passo Se $a$ e $b$ forem expressões regulares então a união $a \cup b$, a concatenação (ou produto) $a\cdot b$ e a iteração $\cl{a}$ também são expressões regulares.

fecho Uma expressão é uma expressão regular se, e só se, pode ser definida através de um número finito de aplicações do passo a partir das expressões da base.

Alguns exemplos de expressões regulares:

$001\cup 110 \simeq (0 \cdot (0 \cdot 1)) \cup ((1\cdot 1) \cdot 0)$.
Qualquer palavra de $\cl{\Sigma}$.
$0 \cdot \cl{(0 \cup1)}$.

Antes de avançar no estudo das ER e LR é importante esclarecer o seguinte ponto importante sobre a notação das expressões regulares:

Regras de Simplificação das Expressões Regulares. A escrita completa de uma expressão regular pode (ainda) ser confusa, por causa dos parêntesis:

$$ (\cl{0} \cup (1 \cdot 0 \cdot (\cl{0}))) \cdot 1 \cdot (\cl{0}) \cdot (((0 \cdot (\cl{1}) \cup (\cl{1})))) $$

Para simplificar esta escrita usam-se as seguintes regras de simplificação:

Sempre que possível não se usa o símbolo da concatenação. Isto é, em vez de $x \cdot y$ escreve-se $xy$.
A iteração $\cl{}$ tem precedência sobre $\cdot$ e sobre $\cup$. Isto é, $0\cdot \cl{1}$ é $0\cdot (\cl{1})$, não $\cl{(0\cdot 1)}$. Igualmente,$0\cup \cl{1}$ é $0\cup (\cl{1})$, não $\cl{(0\cup 1)}$.
A concatenação $\cdot$ tem precedência sobre a união $\cup$. Isto é, $a\cup b\cdot c$ é $a \cup (b \cdot c)$, não $(a \cup b) \cdot c$.

Com estas regras a ER acima fica com o seguinte aspeto: $$ (\cl{0}\cup 10\cl{0})1\cl{0}(0\cl{1}\cup\cl{1}) $$

Diagramas das Expressões Regulares

As expressões regulares podem ser representadas por um diagrama gráfico cuja visualização pode ajudar a entender a sua estrutura.

Diagrama de uma Expressão Regular (Diagrama de Wirth). O diagrama de uma expressão regular é um grafo orientado definido para as operações base e passo da seguinte forma:

Forma da Expressão Regular Tipo Sub-Grafo

$a$ símbolo ou $\lambda$

$xy$ concatenação

$x\cup y$ união

$\cl{x}$ iteração

Forma da Expressão Regular	Tipo	Sub-Grafo
$a$	símbolo ou $\lambda$
$xy$	concatenação
$x\cup y$	união
$\cl{x}$	iteração

Por exemplo, o diagrama da expressão regular $\cl{(11 \cup 0)}\cl{(00 \cup 1)}$ pode ser obtido da seguinte forma:

Operação	Diagrama
Início
Concatenação
Iterações
Uniões

No diagrama final há várias arestas que podem ser eliminadas e ainda continuar a representar a expressão regular inicial. Por exemplo, uma das duas arestas $\nil$ consecutivas, no cento do diagrama, pode ser eliminada.

Operação	Diagrama
Simplificação

Neste caso foi simples detetar uma aresta que podia ser eliminada. Em geral, quais são as arestas que podem ser eliminadas?

Teorema da Eliminação de Arestas Vazias. A aresta pode ser eliminada se:

O vértice $\alpha$ não é final e não saem mais arestas de $\alpha$ ou

O vértice $\beta$ não é inicial e não entram mais arestas em $\beta$.

Alternativamente, a aresta não pode ser eliminada se:

O vértice $\alpha$ é final ou saem mais arestas de $\alpha$ e

O vértice $\beta$ é inicial ou entram mais arestas em $\beta$.

Usando o teorema da eliminação de arestas vazias:

Operação	Diagrama
Simplificação (II)

Semântica das Expressões Regulares

O número quatro pode ser referido de várias formas: IV, 100, 4, quatro, 2+2, etc. Todas essas formas são expressões – texto, sintaxe – cuja interpretação – significado, semântica – é um certo objeto abstrato.

Esta é também a relação entre as linguagens regulares e as expressões regulares: As linguagens são conjuntos (objetos matemáticos, abstratos) que podem ser representados por certas expressões. Isto é, a semântica das ER são as LR. Reciprocamente, as ER são uma sintaxe para as LR. Mais precisamente:

Linguagem Representada por uma Expressão Regular. Qualquer expressão regular sobre $\Sigma$ representa uma certa linguagem, definida pelas seguintes regras:

$L(\empty) = \empty$.

$L(\nil) = \set{\nil}$.

Para cada $a \in \Sigma, L(a) = \set{a}$.

Se $x$ for uma expressão regular então $L(\cl{x}) = \cl{L(x)}$.

Se $x, y$ forem expressões regulares então $L(x \cup y) = L(x) \cup L(y)$.

Se $x, y$ forem expressões regulares então $L(xy) = L(x) L(y)$.

Até aqui, e neste enunciado em particular, estão a ser usados os mesmos símbolos (sintaxe), por exemplo $\empty, \cup, \cl{}$ com significados (semântica) muito diferentes. Por exemplo, “$\cup$” numa ER é apenas um símbolo que liga outras ERs — da mesma forma que + liga \quaddois números\quad duas expressões numéricas. Mas “$\cup$” numa LR é uma operação entre conjuntos, que tem um valor bem definido — tal como 2 + 2 tem um valor bem definido (sob as convenções comuns).

Além disso, foi apenas definida uma função entre ERs e certos conjuntos de palavras – nada afirma, até aqui, que $L(x)$ é regular. Isto é, se $x$ for uma expressão regular então $L(x)$ é uma linguagem. A relação com as linguagens regulares fica esclarecida a seguir:

Equivalência de Expressões e Linguagens Regulares.

Cada expressão regular representa uma linguagem regular. Mais especificamente: Se $x$ for uma expressão regular sobre $\Sigma$ então $L(x)$ é uma linguagem regular sobre $\Sigma$.

Cada linguagem regular pode ser representada por uma expressão regular. Mais especificamente: Se $A$ for uma linguagem regular sobre $\Sigma$ então existe uma expressão regular sobre $\Sigma$, $x$, tal que $A = L(x)$.

Isto é, as expressões regulares denotam exatamente as linguagens regulares e a relação entre umas e outras é a função $L$. Dito de outra forma, as LR são a semântica associada às ER e, reciprocamente, as ER proporcionam uma sintaxe para as LR.

Por exemplo, a linguagem dos inteiros sem sinal e sem $0$ à esquerda (isto é, a representação binária dos números inteiros positivos):

$$ \begin{aligned} \set{0, 1, 10, 11, 100, 101, \ldots} &= \set{0} \cup \set{1}\set{\nil, 0, 1, 00, 01, \ldots} \cr &= \set{0} \cup \set{1}\cl{\set{0, 1}}\cr &= L(0 \cup 1\cl{(0 \cup 1)}) \end{aligned} $$

Há ainda outro tipo importante de equivalência: Depois de fixado o conjunto de símbolos e de operações, duas expressões (sintaxes) muito diferentes podem ter o mesmo valor (semântica).

Por exemplo o número quatro (o objeto matemático abstrato) pode ser representado pelas expressões $4$, $2+2$, $2^2$, etc. Nestes casos escreve-se $2+2 = 4$, $2^2 = 4$ etc. Mas em ALP é preciso cuidado com o sinal “$=$”. As expressões “$4$” e “$2+2$” são sintaticamente diferentes (por exemplo, porque “$4$” tem apenas um símbolo e “$2+2$” tem três) mas equivalentes (a mesma semântica).

Nas linguagens regulares “$A = B$” representa a igualdade entre conjuntos, uma relação matemática. No caso das expressões regulares é necessário esclarecer se se trata de igualdade sintática ou de uma equivalência (isto é, uma igualdade semântica). Por exemplo, $0 \cup 1$ e $1 \cup 0$ são diferentes ao nível sintático: diferem logo no primeiro símbolo. Mas ambas representam a mesma linguagem regular, o conjunto $\set{0, 1}$. Isto é, $L(0 \cup 1) = L(1 \cup 0)$.

Equivalência de Expressões Regulares. Duas expressões regulares, $x, y$, sobre $\Sigma$ são equivalentes, $x \equiv y$, se $L(x) = L(y)$.

No uso comum de expressões regulares pretende-se usar a equivalência, não a igualdade sintática, pelo que “$x = y$” normalmente representa a equivalência, apesar de esta escrita ser um abuso da notação. Isto é, escreve-se $0 \cup 1 = 1 \cup 0$ em vez de $0 \cup 1 \equiv 1 \cup 0$, porque é mais conveniente. Os casos em que se trata a igualdade sintática devem ser explicitamente assinalados como tais.

Propriedades das Expressões Regulares

Sejam $x, y, z$ expressões regulares sobre o alfabeto $\Sigma$. Considerando as operações de união e concatenação:

$$ \begin{aligned} x \cup (y \cup z) &= (x \cup y) \cup z & x(yz) &= (xy)z \cr x \cup \empty &= \empty \cup x = x & x\nil &= \nil x = x \cr && x\empty &= \empty x = \empty \cr x \cup y &= y \cup x \cr x \cup x &= x \cr x(y \cup x) &= xy \cup xz & (x \cup y)z &= xz \cup yz \end{aligned} $$

Para o fecho:

$$ \begin{aligned} \cl{\empty} &= \nil & \cl{\nil} &= \nil \cr \cl{\del{\cl{x}}} &= \cl{x} & \cl{x} &= \nil \cup x\cl{x} \cr x\cl{\del{yx}} &= \cl{\del{xy}} x \cr \cl{\del{x \cup y}} &= \cl{\del{\cl{x} \cup y}} \cr &= \cl{x}\cl{\del{x \cup y}} \cr &= \cl{\del{x \cup y\cl{x}}} \cr &= \cl{(\cl{x}\cl{y})} \cr &= \cl{(\cl{x}y)}\cl{x} \cr &= \cl{x}\cl{(y\cl{x})} \end{aligned} $$

Com estas equivalências uma ER inicialmente complicada (isto é, comprida e/ou profunda) pode ser simplificada. Um exemplo imediato é $\cl{(\cl{(\cl{a})})} = \cl{a}$. Outro exemplo:

$$ a\AST (b \cup (a\AST b\AST)\AST) \alert{a} a\AST (ba\AST)\AST \alert{b} \stackrel{?}{=} (a \cup b)\AST \alert{a}(a \cup b)\AST \alert{b} $$

Aplicando as regras de equivalência $$ \begin{aligned} &a\AST (b \cup \alert{(a\AST b\AST)\AST}) a a\AST (ba\AST)\AST b = & (x\AST y\AST)\AST = (x \cup y)\AST \cr &= a\AST \alert{(b \cup(a \cup b)\AST)} a a\AST (ba\AST)\AST b & y \cup (x \cup y)\AST = (x \cup y)\AST \text{(porquê?)} \cr &= \alert{a\AST (a \cup b)\AST} a a\AST (ba\AST)\AST b & x\AST (x \cup y)\AST = (x \cup y)\AST \cr &= (a \cup b)\AST a \alert{a\AST (ba\AST)\AST} b & x\AST (y x\AST)\AST = (x \cup y)\AST \cr &= (a \cup b)\AST a (a \cup b)\AST b & \text{aceitável… continuando:}\cr &\stackrel{?}{=} \alert{b\AST a} (b\cup a)\AST b \end{aligned} $$

$$ \begin{aligned} &= \alert{(a \cup b)\AST} a (a \cup b)\AST b & x \cup y = y \cup x \cr &= \alert{(b \cup a)\AST} a (a \cup b)\AST b & (x \cup y)\AST = x\AST (y x\AST)\AST \cr &= b\AST\alert{(ab\AST)\AST a} (a \cup b)\AST b & (xy)\AST x= x(yx)\AST \cr &= b\AST a(b\AST a)\AST \alert{(a \cup b)\AST} b & x \cup y = y \cup x \cr &= b\AST a(b\AST a)\AST \alert{(b \cup a)\AST} b & (x \cup y)\AST = (x\AST y)\AST x\AST \cr &= b\AST a\alert{(b\AST a)\AST (b \AST a)\AST} b\AST b & x\AST x\AST = x\AST \text{(porquê?)} \cr &= b\AST a\alert{(b\AST a)\AST b\AST} b & (x\AST y)\AST x\AST = (x \cup y)\AST \cr &= b\AST a (b\cup a)\AST b \end{aligned} $$

As linguagens e expressões regulares são o passo atual para resolver o Problema Principal de ALP (versão 1) – Determinar um sistema computável, eficiente e adequado para definir linguagens de programação.

Nesse sentido importa responder às seguintes questões:

Dada uma linguagem regular $A$, como obter um sistema computável e eficiente para determinar se $p \in A$?

As linguagens regulares são adequadas para definir todas as linguagens de programação? Por exemplo, será possível definir a sintaxe dos programas Python ou Java usando apenas expressões regulares?

Estas questões são resolvidas no próximo capítulo, Autómatos Finitos, onde é definido e estudado um modelo abstrato de computador simples e como este se relaciona com as ER e LR.