Glossário

Glossário de Linguagens Formais e Autômatos

Termos em ordem alfabética, com a nota onde aparecem. Voltar ao mapa. Para o significado de cada símbolo das fórmulas, veja Símbolos e Notação.

Termo	Definição curta	Onde
AFD	autômato finito determinístico: um único próximo estado para cada estado e símbolo, $T:K\times V\to K$	04 - Autômatos Finitos Determinísticos
AFND	autômato finito não determinístico: um conjunto de próximos estados, $T:K\times V\to 2^K$	05 - Autômatos Finitos Não Determinísticos
Alfabeto	conjunto finito de símbolos ($V$ ou $\Sigma$)	01 - Introdução e Conceitos Básicos
Bijeção	função injetora e sobrejetora ao mesmo tempo	02 - Matemática Discreta
Classe de equivalência	$[a]$ = todos os elementos equivalentes a $a$	02 - Matemática Discreta
Concatenação	justapor duas palavras: $wu$	01 - Introdução e Conceitos Básicos
Conjunto quociente	$A/R$, o conjunto das classes de equivalência; forma uma partição	02 - Matemática Discreta
Construção de subconjuntos	algoritmo que transforma AFND em AFD; cada estado do AFD é um conjunto de estados do AFND	06 - Equivalência AFD e AFND
Derivação	aplicação de uma produção: $\alpha \Rightarrow \beta$	03 - Gramáticas Regulares
Enumerável	conjunto que pode ser listado por uma sobrejeção a partir de $\mathbb{N}$	02 - Matemática Discreta
Estado final	estado de aceitação; círculo duplo no diagrama, * na tabela	04 - Autômatos Finitos Determinísticos
Estado inicial	onde a leitura começa; seta solta no diagrama, → na tabela	04 - Autômatos Finitos Determinísticos
Estado poço	estado não final do qual não se sai (morto); completa transições indefinidas	04 - Autômatos Finitos Determinísticos
Expressão regular	descrição de linguagem regular com união, concatenação e fecho	03b - Expressões Regulares
Fecho de Kleene	${\alpha }^{\ast }$: zero ou mais repetições	03b - Expressões Regulares
Fecho reflexivo-transitivo	$R^{\ast }={\bigcup }_{i\ge 0}{R}^i$: “zero ou mais passos”	02 - Matemática Discreta
Fecho transitivo	$R^{+}={\bigcup }_{i\ge 1}{R}^i$: “um ou mais passos”	02 - Matemática Discreta
Forma sentencial	sequência de terminais e não terminais derivada de $S$	03 - Gramáticas Regulares
Função	relação em que cada elemento do domínio tem exatamente uma imagem	02 - Matemática Discreta
Função de transição estendida	$\hat{T}$: aplica $T$ a uma palavra inteira, recursivamente	04 - Autômatos Finitos Determinísticos
Gramática	$G=(V_n,V_t,S,P)$, mecanismo gerador	03 - Gramáticas Regulares
Gramática linear à direita	produções $A\to wB$ ou $A\to w$	03 - Gramáticas Regulares
Gramática regular (tipo 3)	produções $A\to aB$ ou $A\to a$	03 - Gramáticas Regulares
Hierarquia de Chomsky	classificação das gramáticas em tipos 3 ⊂ 2 ⊂ 1 ⊂ 0	03 - Gramáticas Regulares
Injeção	função em que elementos diferentes têm imagens diferentes	02 - Matemática Discreta
Linguagem	conjunto de sentenças sobre um alfabeto, $L\subseteq V^{\ast }$	01 - Introdução e Conceitos Básicos
Linguagem regular	aceita por um AF; equivalentemente, gerada por GR ou descrita por ER	04 - Autômatos Finitos Determinísticos
Não terminal	variável da gramática, elemento de $V_n$	03 - Gramáticas Regulares
Partição	divisão de um conjunto em blocos não vazios, disjuntos, que cobrem tudo	02 - Matemática Discreta
Prefixo / sufixo	trecho inicial / final de uma palavra	01 - Introdução e Conceitos Básicos
Produção	regra de reescrita $\alpha \to \beta$	03 - Gramáticas Regulares
Produção unitária	$A\to B$ (só um não terminal à direita); não é do formato regular	07 - Equivalência AF e GR
Produto cartesiano	$A\times B$, conjunto de pares ordenados	02 - Matemática Discreta
Regra vazia (épsilon)	$S\to \epsilon$	03 - Gramáticas Regulares
Relação de equivalência	reflexiva, simétrica e transitiva	02 - Matemática Discreta
Semântica	significado ou interpretação de um programa	01 - Introdução e Conceitos Básicos
Sentença	palavra, sequência finita de símbolos; na gramática, só terminais	01 - Introdução e Conceitos Básicos
Sentença vazia	$\epsilon$, palavra de tamanho 0	01 - Introdução e Conceitos Básicos
Sintaxe	forma, estrutura, sem considerar significado	01 - Introdução e Conceitos Básicos
Sobrejeção	função que atinge todo o codomínio	02 - Matemática Discreta
Terminal	símbolo que aparece nas palavras geradas, elemento de $V_t$	03 - Gramáticas Regulares
V* e V+	todas as palavras sobre $V$ com e sem $\epsilon$	01 - Introdução e Conceitos Básicos

Símbolos

Símbolo	Leitura
$\epsilon$	palavra vazia
$\varnothing$	conjunto vazio
$|w|$	tamanho da palavra $w$
$w^n$	$w$ concatenada $n$ vezes
$2^K$	conjunto das partes de $K$
$\Rightarrow$, ${\Rightarrow }^{\ast }$, ${\Rightarrow }^{+}$	deriva em 1, em 0 ou mais, em 1 ou mais passos
${\alpha }^{\ast }$, ${\alpha }^{+}$, ${\alpha }^{?}$	zero ou mais, uma ou mais, zero ou uma vez
$\hat{T}$ ou $\check{T}$	função de transição estendida para palavras (os slides desenham o acento invertido)

Termos que aparecem nos livros

Termos que os slides não usam, mas que aparecem no Menezes e no Ramos. As notas explicam cada um.

Termo	Definição curta	Onde
AFε (autômato com movimentos vazios)	autômato que pode mudar de estado sem ler símbolo, $\delta :Q\times (\Sigma \cup \{\epsilon \})\to 2^Q$	08 - Tópicos Complementares dos Livros
Antissimétrica	se $aRb$ e $bRa$, então $a=b$	02 - Matemática Discreta
Autômato mínimo	AFD com o menor número de estados para a linguagem; é único a menos dos nomes	08 - Tópicos Complementares dos Livros
Configuração	par (estado atual, parte da entrada que falta ler)	04 - Autômatos Finitos Determinísticos
Conjunto regular	linguagem montada a partir de $\varnothing$, $\{\epsilon \}$ e $\{a\}$ com união, concatenação e fecho	03b - Expressões Regulares
Derivação não trivial	derivação com pelo menos um passo (${\Rightarrow }^{+}$)	03 - Gramáticas Regulares
Estado inacessível	estado que não pode ser alcançado a partir do inicial	08 - Tópicos Complementares dos Livros
Estado inútil	estado não final do qual não se chega a nenhum final	08 - Tópicos Complementares dos Livros
Fecho vazio	estados alcançáveis a partir de $q$ usando só transições $\epsilon$	08 - Tópicos Complementares dos Livros
Função parcial	função que pode não estar definida para alguns elementos do domínio	02 - Matemática Discreta
Função total	função definida para todos os elementos do domínio	02 - Matemática Discreta
GLD, GLE, GLUD, GLUE	gramáticas lineares à direita, à esquerda, unitárias à direita e à esquerda	03 - Gramáticas Regulares
Impasse	configuração sem transição possível; o caminho morre	05 - Autômatos Finitos Não Determinísticos
Lema do Bombeamento	propriedade de toda linguagem regular, usada para provar que uma linguagem não é regular	08 - Tópicos Complementares dos Livros
Máquina de Mealy	autômato com saída associada às transições	08 - Tópicos Complementares dos Livros
Máquina de Moore	autômato com saída associada aos estados	08 - Tópicos Complementares dos Livros
Metalinguagem	linguagem usada para descrever outra (notação algébrica, BNF, ER)	03 - Gramáticas Regulares
Ordem parcial / total	relação reflexiva, antissimétrica e transitiva / e com todos os pares comparáveis	02 - Matemática Discreta
Prefixo próprio	prefixo diferente da palavra inteira	01 - Introdução e Conceitos Básicos
Propriedade de fechamento	aplicar a operação a linguagens da classe sempre dá uma linguagem da classe	08 - Tópicos Complementares dos Livros
Reconhecedor genérico	fita, cursor, máquina de estados e memória auxiliar opcional	01 - Introdução e Conceitos Básicos
Reverso	$w^R$, a palavra lida de trás para frente	01 - Introdução e Conceitos Básicos
Subpalavra (subcadeia)	qualquer trecho contíguo de uma palavra	01 - Introdução e Conceitos Básicos
Transdutor finito	autômato que escreve uma saída (Mealy ou Moore)	08 - Tópicos Complementares dos Livros