Palavras, linguagens e expressões

Sobre o alfabeto $\{0,1\}$, $0110$ é uma entrada concreta. Se aceitarmos apenas sequências terminadas em $10$, $0110$ pertence à linguagem e $0101$ fica de fora. A palavra é a sequência; a linguagem é o conjunto das sequências que cumprem a condição.

As operações seguintes permitem descrever esses conjuntos. Para conjuntos e relações, usa a revisão de MD.

Alfabetos e palavras

Um alfabeto $\Sigma$ é um conjunto finito e não vazio de símbolos. Uma palavra sobre $\Sigma$ é uma sequência finita desses símbolos. Sobre $\Sigma=\{0,1\}$, tens palavras como $0$, $011$ e $1110$.

A palavra vazia $\varepsilon$ não contém símbolos. O comprimento $|w|$ conta símbolos, logo $|011|=3$ e $|\varepsilon|=0$. Por isso $\varepsilon$ não é uma letra que a máquina tenha de ler.

A concatenação $xy$ escreve $y$ imediatamente depois de $x$. Se $x=01$ e $y=10$, então $xy=0110$ e $yx=1001$. Vale:

$$|xy|=|x|+|y|,\qquad (xy)z=x(yz),\qquad x\varepsilon=\varepsilon x=x.$$

A potência $x^n$ concatena $n$ cópias de $x$, com $x^0=\varepsilon$. Por exemplo, $(01)^3=010101$. O reverso $x^R$ muda a ordem dos símbolos: $(001)^R=100$.

Uma palavra $v$ é subpalavra de $w$ se existem $x,y$ com $w=xvy$. É prefixo quando podes escolher $x=\varepsilon$, e sufixo quando podes escolher $y=\varepsilon$. Em $00101$, $001$ é prefixo, $101$ é sufixo e $010$ é subpalavra. A palavra vazia é prefixo e sufixo de qualquer palavra.

$\Sigma^k$ contém as palavras de comprimento $k$. Assim, $\Sigma^0=\{\varepsilon\}$ e $\{0,1\}^2=\{00,01,10,11\}$. Juntando todos os comprimentos:

$$\Sigma^*=\bigcup_{k\ge0}\Sigma^k, \qquad \Sigma^+=\bigcup_{k\ge1}\Sigma^k=\Sigma^*\setminus\{\varepsilon\}.$$

Se o alfabeto tem $m$ símbolos, há $m^k$ palavras de comprimento $k$, porque cada uma das $k$ posições oferece $m$ escolhas independentes.

Linguagens e operações

Uma linguagem é um conjunto de palavras, $L\subseteq\Sigma^*$. Por exemplo,

$$L=\{0^n1^n\mid n\ge0\}=\{\varepsilon,01,0011,000111,\ldots\}.$$

A condição exige zeros antes dos uns, por isso $0101$ tem tantos zeros como uns mas não pertence a $L$.

Três confusões com ε e ∅

A palavra 01 tem comprimento 2. A linguagem $\{01\}$ tem uma palavra. A linguagem $\{0,1\}^*$ tem infinitas palavras, incluindo $\varepsilon$ e 01. Três erros frequentes:

• escrever $01$ quando queres dizer $\{01\}$;
• escrever $\{\varepsilon\}$ quando queres dizer $\emptyset$;
• ler $A^*$ como “repetir uma palavra de $A$” em vez de “concatenar zero ou mais palavras de $A$”.

Testa cada definição com $\varepsilon$: $\varepsilon \in \{0,1\}^*$, $\varepsilon \in \{a\}^*$, mas $\varepsilon \notin \{a\}^+$. E $\emptyset^*=\{\varepsilon\}$, porque existe uma concatenação vazia, com zero blocos. Não confundas $\emptyset$ com $\{\varepsilon\}$: a primeira linguagem tem zero palavras e a segunda tem uma palavra de comprimento zero, e esta distinção muda o resultado das operações.

Além de união, interseção e diferença de conjuntos, usamos:

$$AB=\{xy\mid x\in A,\ y\in B\},\qquad A^0=\{\varepsilon\},\qquad A^{n+1}=A^nA,$$ $$A^*=\bigcup_{n\ge0}A^n,\qquad A^+=\bigcup_{n\ge1}A^n.$$

O complemento depende do alfabeto: $\overline L=\Sigma^*\setminus L$. Uma palavra que nem usa símbolos de $\Sigma$ não pertence a esse complemento.

Calcular sem perder palavras

Se $A=\{a,ab\}$ e $B=\{\varepsilon,b\}$, enumera os pares:

Palavra de $A$	Palavra de $B$	Concatenação
$a$	$\varepsilon$	$a$
$a$	$b$	$ab$
$ab$	$\varepsilon$	$ab$
$ab$	$b$	$abb$

Portanto, $AB=\{a,ab,abb\}$: três palavras para quatro pares, porque linguagens são conjuntos, não listas com repetições. Já $BA=\{a,ab,ba,bab\}$, logo a concatenação não é comutativa.

Os casos vazios seguem da definição: $A\emptyset=\emptyset A=\emptyset$, enquanto $A\{\varepsilon\}=\{\varepsilon\}A=A$. A estrela contém sempre $\varepsilon$, mesmo em $\emptyset^*=\{\varepsilon\}$.

Provar ou refutar uma igualdade

Para provar $L(M\cup N)=LM\cup LN$, escolhe uma palavra $w$ de cada lado. Se $w=xy$ com $x\in L$ e $y\in M\cup N$, então $y\in M$ ou $y\in N$, logo $w\in LM\cup LN$. O mesmo raciocínio ao contrário prova a outra inclusão.

A igualdade $L(M\cap N)=LM\cap LN$ pode falhar. Usa $L=\{\varepsilon,a\}$, $M=\{a\}$ e $N=\{\varepsilon\}$. O lado esquerdo é vazio, mas $a$ pertence a ambos $LM$ e $LN$, porque as duas concatenações podem decompor a mesma palavra em sítios diferentes.

O mesmo método do elemento arbitrário prova inclusões com estrela. Para $L^*M \subseteq (L+M)^*$, escolhe $w \in L^*M$. Então $w=xy$, com $x \in L^*$ e $y \in M$. Escreve $x=x_1\cdots x_k$, com cada $x_i \in L$. Cada bloco $x_i$ e ainda $y$ pertencem a $L \cup M$. Logo $w$ é uma concatenação de $k+1$ palavras de $L \cup M$, e pertence a $(L+M)^*$. O caso $k=0$ dá $w=y$, que também está incluído. A palavra foi arbitrária, por isso a inclusão vale para todas.

Provas por indução

A definição de palavras permite provar propriedades pelo comprimento. Para mostrar

$$(xy)^R=y^Rx^R,$$

faz indução em $|y|$, mantendo $x$ arbitrário. A base trata a palavra vazia; o passo reduz uma palavra não vazia a uma mais curta e aplica a hipótese só a essa palavra mais curta.

• Base: $y=\varepsilon$. Ambos os lados são $x^R$.
• Passo: escreve $y=za$, com $a\in\Sigma$. A hipótese diz $(xz)^R=z^Rx^R$. Pela definição de reverso, $(xza)^R=a(xz)^R=az^Rx^R=(za)^Rx^R$.

O passo usou a hipótese apenas numa palavra mais curta. Testar exemplos não substitui este argumento para todos os comprimentos.

Há também indução estrutural: provas sobre expressões ou árvores seguem os casos usados para construir esses objetos. Se uma expressão resulta de união, concatenação ou estrela, a prova explica cada uma dessas construções.

Expressões regulares

Uma expressão regular descreve uma linguagem com três operações. As expressões básicas são $\emptyset$, $\varepsilon$ e cada símbolo $a\in\Sigma$. Se $E,F$ são expressões, também o são:

Expressão	Linguagem descrita
$E+F$	$L(E)\cup L(F)$
$EF$	$L(E)L(F)$
$E^*$	$(L(E))^*$

Aqui, $+$ entre expressões significa união. $E^+$ abrevia $EE^*$, ou seja, uma ou mais repetições. A estrela tem maior precedência que a concatenação, e esta tem maior precedência que a união.

Por isso, $01^*+10$ significa um zero seguido de zero ou mais uns, ou a palavra $10$. Não significa repetir $01$. A expressão $(01)^*$ inclui $\varepsilon,01,0101$, enquanto $01^*$ inclui $0,01,011$ e exclui $\varepsilon$.

Descrever uma condição

Sobre $\{a,b\}$, palavras com exatamente dois $b$ têm expressão $a^*ba^*ba^*$. Os dois $b$ são obrigatórios, e os três intervalos de $a$ podem estar vazios.

Palavras que contêm $ab$ têm expressão $(a+b)^*ab(a+b)^*$, porque os lados permitem qualquer prefixo e sufixo. Palavras que terminam em $ab$ têm apenas $(a+b)^*ab$. Testa $aba$: pertence à primeira linguagem, mas não à segunda.

Para palavras binárias sem símbolos iguais consecutivos, podemos usar

$$(\varepsilon+1)(01)^*(\varepsilon+0).$$

As quatro escolhas dos extremos dão comprimentos pares ou ímpares e permitem começar em $0$ ou $1$. Incluem $\varepsilon$, $0$ e $1$. Se a linguagem excluir a palavra vazia, terás de alterar a expressão.

Leis úteis e falsas simplificações

União é comutativa e idempotente: $E+F\equiv F+E$ e $E+E\equiv E$. Concatenação é associativa e distribui sobre união. Temos $E\varepsilon\equiv E$ e $E\emptyset\equiv\emptyset$. O símbolo $\equiv$ indica a mesma linguagem, não o mesmo texto.

Também $(E^*)^*\equiv E^*$ e $E^*E^*\equiv E^*$. Mas $(E+F)^*\equiv E^*+F^*$ é falso: para $E=a,F=b$, o lado esquerdo contém $ab$ e o direito não.

As expressões desta teoria equivalem aos autómatos finitos. Algumas bibliotecas de pesquisa acrescentam operações como referências a grupos anteriores, que ultrapassam este modelo. Para construir as máquinas equivalentes, segue expressões e autómatos.

Provar inclusões com um elemento arbitrário

A técnica usada acima para igualdades serve também para inclusões com estrela. O padrão é sempre o mesmo: escolhe uma palavra arbitrária do lado esquerdo, decompõe-na segundo as operações desse lado e reconstrói-a com as operações do lado direito. Uma única palavra nunca prova a inclusão; uma palavra bem escolhida refuta uma igualdade falsa.