Flashcards de Linguagens Formais e Autômatos
Como usar
Formato do plugin comunitário Spaced Repetition (instale em Configurações > Plugins da comunidade). Com ele, os cartões aparecem para revisão espaçada. Sem o plugin, leia a pergunta, responda em voz alta e só então olhe a resposta (o que vem depois dos dois-pontos duplos, ou abaixo da linha com só uma interrogação). Voltar ao mapa.
Conceitos (01 - Introdução e Conceitos Básicos)
O que é um alfabeto?:: Um conjunto finito de símbolos.
O que é uma sentença sobre V?::Uma sequência finita de símbolos de V.
Qual a diferença entre V* e V+?::V* inclui a palavra vazia ε; V+ = V* − {ε}.
Quantas palavras de tamanho n existem sobre um alfabeto com k símbolos?::k elevado a n.
Autômato é formalismo reconhecedor ou gerador?::Reconhecedor (operacional).
Gramática e expressão regular são reconhecedores ou geradores?::Geradores (axiomático e denotacional, respectivamente).
Uma linguagem L sobre V é um elemento ou um subconjunto de V*?::Um subconjunto: L ⊆ V*.
Matemática discreta (02 - Matemática Discreta)
Quais as três propriedades de uma relação de equivalência?::Reflexiva, simétrica e transitiva.
O que é R*?::O fecho reflexivo-transitivo: união de todas as potências R⁰ ∪ R¹ ∪ R² ∪ … (“zero ou mais passos”).
O que é R+?::O fecho transitivo: R¹ ∪ R² ∪ … (“um ou mais passos”).
Quais as três condições de uma partição?::Blocos não vazios, união dos blocos é o conjunto, blocos disjuntos dois a dois.
Quantas partições tem um conjunto de 5 elementos?::52 (número de Bell B₅).
Nos slides, (R∘S)(x) é igual a quê?::S(R(x)): primeiro R, depois S.
A relação ≠ em ℕ é transitiva?::Não: 1 ≠ 2 e 2 ≠ 1, mas 1 ≠ 1 é falso.
Gramáticas (03 - Gramáticas Regulares)
Quais são os quatro componentes de uma gramática?::Vn (não terminais), Vt (terminais), S (símbolo inicial) e P (produções).
Qual a forma das produções de uma gramática regular (tipo 3)?::A → aB ou A → a.
Ordene os tipos de Chomsky por inclusão.::Tipo 3 ⊂ Tipo 2 ⊂ Tipo 1 ⊂ Tipo 0.
Que máquina reconhece as linguagens do tipo 2?::Autômato com pilha.
Que máquina reconhece as linguagens do tipo 0?::Máquina de Turing.
A linguagem 0ⁿ1ⁿ é regular?::Não. É livre de contexto (S → 01 | 0S1).
Como incluir ε quando S aparece do lado direito de alguma produção?::Criar novo inicial S’, copiar as produções de S para S’ e acrescentar S’ → ε.
O que é uma forma sentencial?::Qualquer sequência de terminais e não terminais derivada de S.
Expressões regulares (03b - Expressões Regulares)
Qual a precedência dos operadores de ER?::Repetição () > concatenação > união (|).
O que significa α+?::αα, uma ou mais repetições.
O que significa α??::α | ε, opcional.
(ab)* é igual a ab?::Não. abab ∈ (ab)* mas ∉ ab; aab ∈ ab mas ∉ (ab).
ER para identificadores (letra seguida de letras ou dígitos)?::L(L|D)
ER para palavras sobre {0,1} sem 00?::(1|01)(0|ε)
Quanto vale ∅?::ε
Uma palavra não vazia pertence a (aba)* se e somente se…::contém pelo menos um b.
Autômatos (04 - Autômatos Finitos Determinísticos e 05 - Autômatos Finitos Não Determinísticos)
Quais os cinco componentes de um AFD?::M = (K, V, T, i, F): estados, alfabeto, função de transição, estado inicial, estados finais.
Qual a assinatura da função de transição de um AFD?::T: K × V → K
Qual a assinatura da função de transição de um AFND?::T: K × V → 2^K
Quando um AFD aceita uma palavra?::Quando, partindo de i e lendo a palavra inteira, termina em um estado de F.
Quando um AFND aceita uma palavra?::Quando pelo menos um caminho possível termina em um estado final.
Passar por um estado final no meio da palavra faz o AFD aceitar?::Não. Só conta o estado depois do último símbolo.
Como se marca o estado inicial e os finais na tabela de transições?::Seta → no inicial, asterisco * nos finais.
Defina T̂ (transição estendida) de um AFD.::T̂(q, ε) = q e T̂(q, ua) = T(T̂(q, u), a).
O que é um estado poço?::Um estado não final de onde não se sai; recebe as transições indefinidas.
O não determinismo aumenta o poder dos autômatos finitos?::Não. Facilita o projeto, mas todo AFND tem um AFD equivalente.
Equivalências (06 - Equivalência AFD e AFND e 07 - Equivalência AF e GR)
Na construção de subconjuntos, o que é cada estado do AFD?::Um conjunto de estados do AFND (os estados ativos).
Como se calcula T’([q0,q1], a)?::T(q0, a) ∪ T(q1, a).
Quais estados do AFD construído são finais?::Os conjuntos que contêm pelo menos um estado final do AFND.
Quantos estados, no máximo, tem o AFD obtido de um AFND com n estados?::2ⁿ
Na conversão AF → GR, o que gera T(B, a) = C com C final e com saídas?::B → aC | a
Na conversão GR → AF, o que gera a produção B → a?::Uma transição de B com a para o novo estado final Z.
Se S → ε está na gramática, o que muda no AF?::O estado inicial S também vira final.
Cartões de várias linhas
Simule o AFD de paridade (F = {q3}, a troca paridade de a, b troca de b) com a palavra abab.
?
q0 → q1 → q3 → q2 → q0. Termina em q0, não final: rejeita (2 a e 2 b, ambos pares).
Converta para AFD o estado [q0,q1] do AFND do slide 9 da aula 06 (T(q0,0)={q1}, T(q1,0)={q0,q1}, T(q0,1)={q2}, T(q1,1)={q0}).
?
Com 0: {q1} ∪ {q0,q1} = [q0,q1]. Com 1: {q2} ∪ {q0} = [q0,q2].
Derive 0101010 em S → ASBB | BSAA | 0, A → 01 | 01A, B → 10 | 10B.
?
S ⇒ ASBB ⇒ 01SBB ⇒ 010BB ⇒ 01010B ⇒ 0101010
Cartões dos livros (Menezes e Ramos)
Para o Menezes, a função de transição de um AFD é total ou parcial?::Parcial. Transição indefinida faz o autômato parar e rejeitar.
Quais são as três formas de um AFD parar (Menezes)?::Aceita (leu tudo e está em estado final), rejeita (leu tudo e está em estado não final) ou rejeita por transição indefinida.
Um AFD com n estados e m símbolos e função total tem quantas transições?::Exatamente m·n (Ramos).
No Menezes, (g∘f)(a) é igual a quê?::g(f(a)): aplica primeiro f. É a ordem contrária à dos slides.
O Menezes considera o conjunto vazio um alfabeto?::Sim. O Ramos não: para ele o alfabeto é finito e não vazio.
Se ε ∈ L, quanto vale L⁺?::L⁺ = L*. A igualdade L⁺ = L* − {ε} só vale se ε ∉ L.
O que é o fecho vazio de um estado?::O conjunto de estados alcançáveis a partir dele usando zero ou mais transições ε.
Transições vazias aumentam o poder dos autômatos finitos?::Não. Todo AFε tem um AFND equivalente sem ε.
Quais os pré-requisitos para minimizar um AFD (Menezes)?::Ser determinístico, não ter estados inacessíveis e ter função de transição total.
Qual o primeiro passo do algoritmo de minimização por tabela?::Marcar todos os pares (estado final, estado não final).
O autômato mínimo de uma linguagem regular é único?::Sim, a menos do nome dos estados.
Enuncie o Lema do Bombeamento.::Se L é regular, existe n tal que toda w ∈ L com |w| ≥ n se escreve w = uvz com |uv| ≤ n, |v| ≥ 1 e uvⁱz ∈ L para todo i ≥ 0.
O Lema do Bombeamento serve para provar que uma linguagem é regular?::Não. Só serve para provar que NÃO é regular.
Que palavra usar para provar que aⁿbⁿ não é regular?::w = aⁿbⁿ. Como |uv| ≤ n, v só tem a, e bombear quebra o equilíbrio.
As linguagens regulares são fechadas para quais operações?::União, concatenação, fecho, complemento e interseção.
Por que o AFD precisa ser total para complementar trocando os finais?::Porque senão palavras rejeitadas por indefinição continuariam rejeitadas nos dois autômatos.
Como decidir se um AF com n estados aceita uma linguagem infinita?::Verificar se aceita alguma palavra com n ≤ |w| < 2n.
Diferença entre Mealy e Moore?::Mealy: saída nas transições. Moore: saída nos estados.
Mealy e Moore são equivalentes?::Sim, exceto para a entrada vazia (Moore escreve a saída do estado inicial, Mealy não escreve nada).
Na Hierarquia de Chomsky, o que as livres de contexto expressam que as regulares não?::Aninhamento (parênteses balanceados, blocos).
Por que “declarar antes de usar” não é livre de contexto?::Porque liga dois pontos distantes da mesma cadeia (dependência de contexto), como em {wcw}.
Como converter X → Y (produção unitária) em autômato, segundo o Ramos?::Com uma transição vazia de X para Y.
Na conversão AF → GR do Menezes e do Ramos, o que gera um estado final X?::A produção X → ε.