# NFA e transições vazias Percursos alternativos, fecho-ε, determinização e complemento de uma linguagem reconhecida por NFA. Página: https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/ No [DFA do sufixo $ab$](https://resumos.rgo.pt/cadeiras/tc/automatos-finitos/#construir-estados-com-significado), cada letra determina o próximo estado. Um **NFA** pode manter o ciclo que lê o prefixo e, ao mesmo tempo, começar um ramo que tenta verificar o sufixo; uma escolha errada bloqueia esse ramo, mas basta um ramo consumir a palavra toda e terminar num final. ## Aceitação é existência de um percurso Um **NFA** tem os mesmos cinco componentes de um DFA, mas $$ \delta:Q\times\Sigma\to\mathcal P(Q). $$ O destino é um conjunto: pode conter zero, um ou vários estados. $\mathcal P(Q)$ é o conjunto de todos os subconjuntos de $Q$. Um ramo sem transição morre, sem impedir que outro ramo aceite. Um NFA aceita $w$ se existe pelo menos um percurso de $q_0$ até um estado final que lê exatamente $w$. Não exige que todos os percursos aceitem, e não pode aceitar deixando símbolos por ler. Para o sufixo $01$, com conjuntos de estados fáceis de seguir, usa esta tabela: | Estado | $0$ | $1$ | | --- | --- | --- | | $p$ inicial | $\{p,q\}$ | $\{p\}$ | | $q$ | $\emptyset$ | $\{r\}$ | | $r$ final | $\emptyset$ | $\emptyset$ | ![NFA para palavras terminadas em 01: p repete 0 e 1, pode escolher ir a q num 0 e chega ao final r num 1.](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/figura-1.svg) O ciclo em $p$ lê o prefixo. A transição $p\xrightarrow{0}q$ escolhe o início do sufixo. Como $r$ não tem saídas, essa escolha só aceita se o $1$ for a última letra. Para simular sem adivinhar, mantém o conjunto de estados possíveis. Se $S$ é o conjunto atual, depois de ler $a$ tens $\bigcup_{q\in S}\delta(q,a)$. Para $001$: $$ \{p\}\xrightarrow{0}\{p,q\} \xrightarrow{0}\{p,q\} \xrightarrow{1}\{p,r\}. $$ Como o conjunto final contém $r$, a palavra é aceite. Com mais um $0$, chegas a $\{p,q\}$ e a palavra $0010$ é rejeitada. Experimenta $001$ e $0010$. O laboratório mantém todos os ramos: chegar a $r$ antes do fim não basta. Abre o editor para acrescentar um destino ou alterar os estados finais. ## Construir um NFA por adivinhação Para reconhecer palavras binárias cujo antepenúltimo símbolo é $1$, adivinha onde começa esse sufixo de comprimento 3. Usa quatro estados em linha: $p$ repete $0,1$; num $1$ pode saltar para $q$; depois $q \xrightarrow{0,1} r \xrightarrow{0,1} s$, com $s$ final e sem saídas. Para $1101$, o ramo que salta no segundo $1$ lê depois $01$ e aceita em $s$, e o ramo que salta no primeiro $1$ lê depois $101$ e bloqueia por falta de transição, sem que isso impeça a aceitação. Também $1100$ é aceite, pois o segundo $1$ é o antepenúltimo símbolo e o ramo que o escolhe lê os dois $0$ até $s$. Já $1000$ é rejeitada: o salto no único $1$ chega a $s$ depois de ler dois $0$, mas resta um terceiro $0$ e $s$ não tem saídas. A palavra vazia e as palavras com menos de três símbolos são rejeitadas pelo mesmo motivo, porque nenhum ramo chega a $s$. Este é o padrão de adivinhação: um ciclo consome o prefixo, uma transição escolhe a posição relevante, e uma cauda curta verifica o sufixo. A determinização transforma essa adivinhação em conjuntos de estados possíveis. ## De NFA para DFA: construção de subconjuntos O DFA equivalente guarda um conjunto inteiro como um único estado. O estado inicial é $\{q_0\}$ e a transição é: $$ \delta_D(S,a)=\bigcup_{q\in S}\delta_N(q,a). $$ Um subconjunto é final se intersecta $F$. A tabela do exemplo fica: | Estado do DFA | $0$ | $1$ | Final? | | --- | --- | --- | --- | | $A=\{p\}$ inicial | $B$ | $A$ | Não | | $B=\{p,q\}$ | $B$ | $C$ | Não | | $C=\{p,r\}$ | $B$ | $A$ | Sim | Constrói a tabela por rondas, mantendo uma lista de trabalho: 1. Começa com o subconjunto inicial $\{q_0\}$. 2. Para cada subconjunto na lista e cada letra, calcula a união dos destinos e o seu fecho, se houver transições vazias. 3. Acrescenta à lista os subconjuntos novos e repete até não surgir nenhum. 4. Marca como final cada subconjunto que intersecta $F$. Só precisas dos subconjuntos alcançáveis, não de desenhar todos os $2^{|Q|}$ candidatos. O conjunto vazio, se aparecer, é um estado poço como os outros: a união de destinos a partir dele continua vazia. O limite geral é $2^{|Q|}$ estados, e não $2|Q|$. Neste exemplo só surgem três. Ideia-chave da correção O estado do DFA depois de $x$ é exatamente o conjunto dos estados que o NFA pode alcançar lendo $x$. A igualdade vale no início e a união de destinos preserva-a ao acrescentar uma letra, por isso ambos aceitam as mesmas palavras. ## Transições ε e fecho-ε Num **ε-NFA**, permite $\delta:Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal P(Q)$. Uma transição $\varepsilon$ muda de estado sem consumir entrada. O fecho-$\varepsilon$ $E(S)$ contém todos os estados alcançáveis de algum estado de $S$ com zero ou mais transições vazias. Inclui sempre $S$. Para o calcular, começa com $S$ e segue saídas vazias até não encontrar estados novos. Um ciclo vazio não impede o algoritmo de terminar, porque há finitos estados e cada estado entra uma vez no conjunto. Considera a máquina para $a^*b^*$: ![ε-NFA para a estrela seguida de b estrela. p repete a; uma transição vazia leva a q, final, que repete b.](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/figura-2.svg) $E(\{p\})=\{p,q\}$ e $E(\{q\})=\{q\}$. A palavra vazia é aceite porque o fecho do início contém um final. A transição vazia não obriga a mudar para $q$; o ramo em $p$ continua disponível para ler mais $a$. Compara a entrada vazia, $aab$ e $abba$. Cada linha mostra os destinos que consomem a letra e o fecho-ε desses destinos. No editor, o símbolo ε está disponível sem pertencer ao alfabeto. ## Determinizar com fechos Agora, o estado inicial do DFA é $E(\{q_0\})$, e cada passo é: $$ \delta_D(S,a)=E\left(\bigcup_{q\in S}\delta(q,a)\right). $$ Os conjuntos guardados já estão fechados. Se começares por um conjunto arbitrário não fechado, aplica o fecho antes de consumir a letra também. Para a máquina anterior: | Estado | $a$ | $b$ | Final? | | --- | --- | --- | --- | | $A=\{p,q\}$ inicial | $A$ | $B$ | Sim | | $B=\{q\}$ | $C$ | $B$ | Sim | | $C=\emptyset$ | $C$ | $C$ | Não | O $a$ em $B$ leva ao poço porque, depois de começar os $b$, não pode haver outro $a$. Simular $abba$ percorre $A,A,B,B,C$ e rejeita. $aab$ termina em $B$ e aceita. Para eliminar apenas as transições vazias, mantendo um NFA, podes definir $$ \delta'(q,a)=E\left(\bigcup_{p\in E(\{q\})}\delta(p,a)\right) $$ e marcar $q$ como final quando $E(\{q\})\cap F\ne\emptyset$. Isto também preserva a aceitação da palavra vazia. ## Complementar depois de determinizar Trocar finais e não finais num NFA não produz, em geral, o complemento. A aceitação exige **algum** ramo final; a rejeição exige que **nenhum** ramo seja final. Trocar estados não troca esses quantificadores. O procedimento correto é construir o DFA completo equivalente e trocar os finais nesse DFA. No exemplo $a^*b^*$, apenas $C$ fica final. Assim, $abba$ passa a ser aceite, enquanto $aab$ e $\varepsilon$ passam a ser rejeitadas. DFA, NFA e ε-NFA reconhecem a mesma classe, as **linguagens regulares**. O não determinismo pode reduzir o tamanho da descrição, mas não aumenta o poder deste modelo. Para aumentar a descrição sem mudar o poder, a [conversão por Thompson](https://resumos.rgo.pt/cadeiras/tc/expressoes-automatos/#express%C3%A3o-para-%CE%B5-nfa-thompson) segue a direção inversa. ## Exercícios Os problemas são originais, salvo as adaptações identificadas no enunciado. Fechos num ciclo Um ε-NFA tem estados $p,q,r,s$ e apenas as transições vazias $p\to q$, $q\to r$ e $r\to q$. Calcula $E(\{p\})$, $E(\{r\})$ e $E(\{p,s\})$. Explica como garantir que o cálculo termina. Pista Segue só as setas vazias, na direção indicada. Solução De $p$, chegamos a $q$ e depois a $r$, logo $E(\{p\})=\{p,q,r\}$. De $r$, chegamos a $q$ e voltamos a $r$, mas nunca chegamos a $p$: $E(\{r\})=\{q,r\}$. O estado $s$ não tem saídas e pertence ao próprio fecho, por isso $E(\{p,s\})=\{p,q,r,s\}$. Mantemos um conjunto de visitados e uma lista dos estados novos ainda por explorar. Cada estado entra na lista uma única vez. O ciclo não acrescenta estados depois de visitar $q,r$, e há apenas quatro estados. Confere a tua resposta: * Incluí os estados de partida em cada fecho. * Respeitei a direção das arestas, sem chegar de r a p. * Justifiquei terminação com estados visitados. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/#transi%C3%A7%C3%B5es-%CE%B5-e-fecho-%CE%B5) Trocar finais? Um NFA tem, para a mesma palavra, um percurso final e um percurso não final. Trocar todos os estados finais com os não finais rejeita necessariamente essa palavra? Pista Antes e depois da troca, pergunta se existe algum percurso final. Mais uma pista O percurso antes não final passa a final; o percurso antes final passa a não final. Solução Não. Antes existe um ramo aceitante; depois também existe, agora pelo outro percurso. A palavra é aceite pelas duas máquinas, portanto a segunda não reconhece o complemento. O complemento obtém-se num DFA completo equivalente. * **Não; determiniza, completa e só depois troca finais..** A aceitação existencial do NFA não se complementa trocando estados. * **Sim, qualquer NFA pode ser complementado dessa forma..** Uma palavra pode ter simultaneamente um ramo final e outro não final. * **Não existe autómato para o complemento..** O complemento de uma regular é regular. Erros frequentes Não troques a existência de um ramo por aceitação de todos os ramos. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/#complementar-depois-de-determinizar) Determinizar uma tabela Um NFA tem início $p$, final $q$, e transições $\delta(p,a)=\{p,q\}$, $\delta(p,b)=\{p\}$, $\delta(q,a)=\delta(q,b)=\emptyset$. Constrói o DFA equivalente e descreve a linguagem. Pista Começa em $\{p\}$ e calcula as uniões de destinos. Mais uma pista De $\{p,q\}$, a dá $\{p,q\}$ e b dá $\{p\}$. Solução Os estados são $A=\{p\}$ e $B=\{p,q\}$. Ambos levam a B por a e a A por b. A é inicial e B é o único final. Portanto, reconhece as palavras terminadas em a. O ramo que sai de p para q tem de ler a última letra, porque q não tem saídas. Confere a tua resposta: * Obtém exatamente os dois subconjuntos alcançáveis. * Dá uma saída por letra para cada subconjunto. * Marca como final todo subconjunto que contém q. Erros frequentes Não marques A como final só porque alcança q. Não acrescentes o vazio se ele não for alcançável neste exemplo. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/#de-nfa-para-dfa-constru%C3%A7%C3%A3o-de-subconjuntos) Fechar antes e depois Um ε-NFA sobre $\{a,b\}$ tem início $p$, único final $r$ e apenas estas transições: $p\xrightarrow{\varepsilon}q$, $q\xrightarrow{a}q$, $q\xrightarrow{b}r$, $r\xrightarrow{\varepsilon}q$. Constrói a tabela do DFA completo equivalente. A palavra vazia é aceite? E $bab$? Pista Calcula primeiro os três fechos individuais. Mais uma pista $E(\{p\})=\{p,q\}$, $E(\{q\})=\{q\}$ e $E(\{r\})=\{q,r\}$. Solução Os estados alcançáveis são $A=\{p,q\}$, $B=\{q\}$ e $C=\{q,r\}$. A tabela é: | Estado | $a$ | $b$ | Final? | | --- | --- | --- | --- | | $A$ inicial | $B$ | $C$ | Não | | $B$ | $B$ | $C$ | Não | | $C$ | $B$ | $C$ | Sim | Não aparece o conjunto vazio: cada subconjunto alcançável contém $q$, que tem saída pelas duas letras. A máquina já é completa. $\varepsilon$ acaba em $A$ e rejeita; $bab$ segue $A,C,B,C$ e aceita. A linguagem é a das palavras terminadas em $b$. Confere a tua resposta: * Começa no fecho de p, incluindo q. * Fecha os destinos depois de cada letra, incluindo q quando chega a r. * Justifica por que o vazio não é alcançável e identifica os subconjuntos finais. Erros frequentes Não confundas completo com ter obrigatoriamente um poço. Não esqueças a saída vazia de r, que permite ler mais letras depois de o alcançar. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/#determinizar-com-fechos) Antepenúltimo bit Constrói um NFA para palavras binárias cujo antepenúltimo símbolo é $1$. Dá todas as transições e o único final. Segue $1101$, $1100$, $1000$ e $\varepsilon$, indicando um ramo aceitante quando exista. Pista Conta quantas letras restam depois de cada possível salto. Solução Usa início $p$ e único final $s$. As transições são $\delta(p,0)=\{p\}$, $\delta(p,1)=\{p,q\}$, $\delta(q,0)=\delta(q,1)=\{r\}$ e $\delta(r,0)=\delta(r,1)=\{s\}$. De $s$ não há saídas. Em $1101$, o ramo $p\xrightarrow{1}p\xrightarrow{1}q\xrightarrow{0}r\xrightarrow{1}s$ aceita. Em $1100$, o mesmo salto no segundo $1$ lê $00$ e também aceita. Em $1000$, o único salto para $q$ chega a $s$ com um $0$ por ler, pelo que falha. O ramo que permanece em $p$ não é final. $\varepsilon$ termina em $p$ e rejeita. Cada ramo que chega a $s$ consumiu exatamente duas letras após escolher um $1$. Inversamente, quando o antepenúltimo bit é $1$, o ramo que o escolhe termina em $s$ depois da última letra. Confere a tua resposta: * Dei a tabela completa do NFA, com conjuntos vazios em s. * Aceitei 1101 e 1100 pelo salto no segundo 1. * Rejeitei 1000 por entrada restante e ε por início não final. * Justifiquei a condição em ambas as direções. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/tc/automatos-nao-deterministas/#construir-um-nfa-por-adivinha%C3%A7%C3%A3o) ## Experimentar as construções Depois de resolver os problemas, compara os conjuntos do teu DFA com a execução do ε-NFA de «Fechar antes e depois» e do NFA de «Antepenúltimo bit». Em Resolver exercício, corrige a transição alterada ou constrói a tua máquina do zero. A verificação procura uma palavra que distinga a tua máquina da referência.