00 - Mapa da Disciplina

Linguagens Formais e Autômatos · Mapa da Disciplina

Como usar este vault

Cada aula (um PDF de slides) virou uma nota com a explicação slide a slide, exercícios resolvidos em blocos recolhíveis (clique para abrir, tente antes!), diagramas dos autômatos e um trecho final dizendo onde aprofundar nos livros. Abra o mapa mental para a visão geral e use a visão de grafo (Ctrl/Cmd + G) para ver como as notas se ligam.

Ordem de estudo

flowchart LR
  A[01 Conceitos] --> B[02 Matemática<br/>Discreta]
  B --> C[03 Gramáticas]
  C --> D[03b Expressões<br/>Regulares]
  D --> E[04 AFD]
  E --> F[05 AFND]
  F --> G[06 AFD ≡ AFND]
  G --> H[07 AF ≡ GR]
  C -.-> H
  H --> I[08 Complementos<br/>dos livros]

#	Nota	Slides	Ideia central
01	01 - Introdução e Conceitos Básicos	Conceitos.pdf	alfabeto, sentença, linguagem; reconhecer × gerar
02	02 - Matemática Discreta	01_MatematicaDiscreta.pdf	conjuntos, funções, relações, R*, equivalência
03	03 - Gramáticas Regulares	03_GramaticasRegulares.pdf	G=(Vn,Vt,S,P), derivação, Hierarquia de Chomsky
03b	03b - Expressões Regulares	03b_ExpresssoesRegulares.pdf	união, concatenação, fecho de Kleene
04	04 - Autômatos Finitos Determinísticos	04_AutomatosFinitos.pdf	M=(K,V,T,i,F), T: K×V→K
05	05 - Autômatos Finitos Não Determinísticos	05_AutomatosNaoDeterministicos.pdf	T: K×V→2^K, aceita se algum caminho aceita
06	06 - Equivalência AFD e AFND	06_EquivalenciaAFDeAFND.pdf	construção de subconjuntos
07	07 - Equivalência AF e GR	07_EquivalenciaAFDeGR.pdf	estado ↔ não terminal, transição ↔ produção
08	08 - Tópicos Complementares dos Livros	livros (Menezes cap. 2, Ramos cap. 3)	AF com ε, minimização, bombeamento, fechamento, Mealy e Moore

Complementos dos livros

Cada nota de 01 a 07 tem agora uma seção “Aprofundamento com os livros”, com o que o Menezes e o Ramos acrescentam, onde eles discordam dos slides, exercícios extras resolvidos e as páginas exatas das edições da pasta. A nota 08 reúne os tópicos que os livros cobrem logo depois do ponto onde os slides param. Veja Referências - Livros para saber qual livro usar para quê.

Material de apoio: Símbolos e Notação · Glossário · Flashcards · Referências - Livros · Mapa mental (Canvas)

Checklist de estudo

• 01 · Ler e responder a autoavaliação
• 02 · Refazer a composição R∘S do slide 16 sem olhar
• 02 · Listar as partições de {a,b,c,d} (são 15)
• 03 · Refazer as duas derivações do slide 12
• 03 · Classificar 3 gramáticas na Hierarquia de Chomsky
• 03b · Escrever as ERs do slide 14 sem olhar
• 04 · Descobrir a linguagem dos AFDs dos slides 12 a 14 pelo invariante
• 05 · Simular abbaba com conjunto de estados ativos
• 06 · Converter o exercício 1 (alfabeto a, b, c) para AFD
• 07 · Fazer GR → AF e AF → GR dos slides 11 e 12
• 02 · Refazer o exercício 1.18 do Menezes (a “prova” dos gremistas) e achar o erro
• 04 · Fazer os AFDs do exercício 2.2 do Menezes antes de abrir as respostas
• 08 · Minimizar um AFD pelo algoritmo da tabela
• 08 · Provar com o Lema do Bombeamento que $a^n{b}^n$ não é regular
• Revisar os Flashcards

A grande ideia da disciplina até aqui

flowchart TB
  L((Linguagens<br/>regulares))
  ER[Expressão regular<br/>gera · denotacional] --- L
  GR[Gramática regular<br/>gera · axiomático] --- L
  AFD[AFD<br/>reconhece · operacional] --- L
  AFND[AFND<br/>reconhece · operacional] --- L

Quatro jeitos diferentes de descrever a mesma classe de linguagens. As aulas 06 e 07 provam parte dessas equivalências. O próximo nível da Hierarquia de Chomsky (linguagens livres de contexto, autômatos com pilha) provavelmente vem nas próximas aulas.

Pontos dos slides que merecem conferência com o professor

Ao conferir os exercícios por programa e reler as definições, encontrei alguns trechos que parecem erro de digitação ou que podem gerar confusão. Estão marcados com o bloco “bug” nas notas:

Aula	Slide	O que chama atenção	Nota
01 Conceitos	21	”$L\in V^{\ast }$ é finita”: deveria ser $L\subseteq V^{\ast }$, e linguagens podem ser infinitas	01 - Introdução e Conceitos Básicos
02 Mat. Discreta	2	”incontável” definido como denso ($\mathbb{Q}$ é denso e contável)	02 - Matemática Discreta
02 Mat. Discreta	8	suc: ℤ × ℤ em vez de suc: ℤ → ℤ	02 - Matemática Discreta
03 Gramáticas	4	$a^n{b}^n{c}^n$ com $n<0$	03 - Gramáticas Regulares
03 Gramáticas	16	$S\to Ba$ provavelmente seria $S\to bA$	03 - Gramáticas Regulares
03b ER	4	”α e β ∈ Vt” em vez de “α e β são ERs”	03b - Expressões Regulares
03b ER	8	$1^{\ast }(101{)}^{\ast }{1}^{\ast }$ não gera todas as palavras sem 00	03b - Expressões Regulares
05 AFND	11	índice $q\in P$ em vez de $q\in Q$	05 - Autômatos Finitos Não Determinísticos
06 Equivalência	4	$T^{\prime }:K^{\prime }\times V_t\to 2^{K^{\prime }}$ em vez de $\to K^{\prime }$	06 - Equivalência AFD e AFND
07 AF e GR	12	$S\to C$ é produção unitária, fora do formato regular	07 - Equivalência AF e GR

Nenhum desses muda a ideia principal da aula, mas vale saber para não estranhar na hora da prova.

Como as respostas foram conferidas

Montei um pequeno programa que simula cada autômato dos slides, gera as palavras de cada gramática e testa cada expressão regular contra a descrição da linguagem, para todas as palavras até um certo tamanho (em geral 8 a 13 símbolos). Quando uma nota diz “conferido por programa”, foi isso. É uma verificação forte, mas não é uma prova matemática: para palavras maiores do que o limite testado, a garantia vem do raciocínio explicado na nota.

Recursos do Obsidian usados aqui

• Callouts recolhíveis (> [!example]-) para esconder as respostas.
• LaTeX ($...$) para a notação formal.
• Mermaid para fluxogramas e mapas de conceito.
• Imagens SVG dos autômatos na pasta assets (geradas com Graphviz, com fundo branco para ler bem no tema escuro).
• Canvas para o mapa mental.
• Propriedades (frontmatter) com aula, fonte, tags e aliases, o que permite buscar por tag:#afd ou pelo apelido “AFND”.
• Flashcards no formato do plugin comunitário Spaced Repetition (opcional; sem o plugin a nota continua legível).