01 · Introdução e Conceitos Básicos

Resumo em 30 segundos

Linguagens formais estudam a forma (sintaxe) das linguagens, não o significado. Tudo parte de três peças: alfabeto (conjunto finito de símbolos), sentença (sequência finita de símbolos) e linguagem (conjunto de sentenças). Os formalismos que usamos para descrever linguagens são de três tipos: operacional (autômatos, que reconhecem), axiomático (gramáticas, que geram) e denotacional (expressões regulares, que geram).

Voltar para o mapa da disciplina · Próxima: 02 - Matemática Discreta

---

Slide 1 e 2: roteiro da aula

A aula cobre: sintaxe e semântica, tratamento (os tipos de formalismo), alfabetos, sentenças e linguagens. O rodapé de todos os slides avisa: ler slides não substitui o estudo do material de referência. Por isso cada nota deste vault termina com uma seção apontando onde aprofundar nos livros.

Slide 3: de onde vem a teoria

• A Teoria das Linguagens Formais foi desenvolvida na década de 1950, com Noam Chomsky como nome central.
• O objetivo inicial era estudar linguagens naturais (português, inglês).
• Logo se percebeu que a teoria servia muito bem para linguagens artificiais, principalmente as da computação (linguagens de programação).

Slide 4: onde isso é usado

Área	Exemplo prático
Compiladores	análise léxica (tokens) e análise sintática (estrutura do código)
Hardware	modelagem de circuitos e redes lógicas
Biologia	modelagem de sistemas biológicos (sequências de DNA, por exemplo)
Mais recente	animações e jogos, hipertexto e hipermídia, linguagens não lineares

Ligação com o que você já usa

Quando você escreve uma regex em JavaScript para validar um e-mail, ou quando o TypeScript aponta um erro de sintaxe, você está usando resultados diretos desta disciplina. O analisador léxico de um compilador é, na prática, um autômato finito (ver 04 - Autômatos Finitos Determinísticos).

Slides 5 a 9: sintaxe × semântica

A ideia central é separar duas perguntas:

	Sintaxe	Semântica
Pergunta	”Isso está bem escrito?"	"O que isso significa?”
Trata de	propriedades livres da linguagem, sem significado	a interpretação, o valor ou efeito do programa
Exemplo	verificar se o programa respeita a gramática	calcular o que o programa faz

Pontos que os slides destacam:

1. Historicamente a sintaxe veio primeiro: foi reconhecida antes, recebeu tratamento adequado antes e é mais simples de tratar.
2. Consequência: por um tempo se achou que as questões de linguagens de programação se resumiam à sintaxe. Não se resumem.
3. A teoria da sintaxe tem construções matemáticas bem definidas e universalmente aceitas, como as gramáticas de Chomsky (ver 03 - Gramáticas Regulares).
4. Sintaticamente errado = nem é um programa da linguagem. Sintaticamente correto = é um programa, mas pode não fazer o que o programador quer. “Correto” de verdade depende de o programa modelar o comportamento desejado (isso já é semântica).
5. A fronteira nem sempre é clara (o slide cita a ocorrência de um nome em um programa: declarar antes de usar é sintaxe ou semântica?). Em linguagens artificiais a distinção costuma ser mais óbvia.
6. Análise léxica é um tipo especial de análise sintática, focada nos componentes básicos (palavras, números, identificadores). É a ênfase da disciplina.

flowchart LR
  A[Código-fonte] --> B[Análise léxica<br/>autômatos finitos / ER]
  B -->|tokens| C[Análise sintática<br/>gramáticas]
  C -->|árvore| D[Análise semântica]
  D --> E[Geração de código]
  style B fill:#dbe7ff,stroke:#2b4c9b
  style C fill:#dbe7ff,stroke:#2b4c9b

Em azul: as fases que a disciplina de Linguagens Formais sustenta diretamente.

Slides 10 a 13: os três tipos de formalismo

flowchart TB
  F[Formalismos para descrever linguagens] --> O[Operacional]
  F --> AX[Axiomático]
  F --> DN[Denotacional ou Funcional]
  O --> O1["Autômato / máquina abstrata<br/>RECONHECEDOR"]
  AX --> AX1["Gramática<br/>GERADOR"]
  DN --> DN1["Expressão Regular<br/>GERADOR"]

• Operacional (slide 11): define-se uma máquina abstrata com estados, instruções primitivas e a especificação de como cada instrução muda o estado. A máquina é simples o bastante para não deixar dúvida sobre sua execução. É um formalismo reconhecedor: recebe uma entrada e responde se ela é “reconhecida”. Exemplo: autômato finito.

• Axiomático (slide 12): associam-se regras aos componentes da linguagem. As regras dizem o que passa a ser verdade depois de aplicar cada cláusula, considerando o que era verdade antes. É um formalismo gerador. Exemplo: gramática.

• Denotacional ou funcional (slide 13): define-se um domínio que caracteriza as palavras admissíveis; o valor de uma construção é calculado a partir dos valores das suas partes (composicionalidade). Na disciplina, essa abordagem fica restrita às expressões regulares. Também é gerador.

Reconhecer × gerar

Reconhecedor: “me dá uma palavra que eu digo sim ou não”. Gerador: “eu produzo todas as palavras da linguagem”. As aulas 06 e 07 mostram que, para linguagens regulares, os dois lados têm o mesmo poder.

Slide 14: o que é uma linguagem

• Linguagem é um meio de comunicação usado pelos elementos de uma comunidade.
• É formada por um conjunto de palavras e um conjunto de regras gramaticais.
• É formal quando pode ser representada por um sistema matemático com sintaxe e semântica.

Slide 15: alfabeto

Alfabeto (ou vocabulário) é um conjunto finito de símbolos.

• $\{a,b,c,\dots ,z\}$
• $\{0,1\}$
• $\{\text{for},\text{if},\text{do},\text{while},⟨nome⟩,⟨valor⟩\}$

Um símbolo pode ter vários caracteres

No terceiro exemplo, while é um símbolo. Isso é exatamente o que acontece depois da análise léxica: o analisador sintático enxerga tokens, não letras.

Slides 16 e 17: sentença, tamanho, V* e V+

Sentença (palavra, string) sobre um alfabeto $V$ é qualquer sequência finita de símbolos de $V$.

• Com $V=\{0,1\}$: 001, 1010 são sentenças.
• Tamanho $|w|$ = número de símbolos. Com $V=\{a,b,c\}$ e $w=\text{ababcbba}$, temos $|w|=8$.
• Sentença vazia $\epsilon$: não tem símbolos, $|\epsilon |=0$.

Notação	Significado	Exemplo com $V=\{0,1\}$
$V^{\ast }$	todas as sentenças sobre $V$, inclusive $\epsilon$	$\{\epsilon ,0,1,00,01,10,11,000,\dots \}$
$V^{+}$	$V^{\ast }-\{\epsilon \}$	$\{0,1,00,01,10,11,000,\dots \}$

Quantas palavras de tamanho n?

Se $|V|=k$, existem exatamente $k^n$ palavras de tamanho $n$. Com $\{0,1\}$ e $n=3$: $2^3=8$ palavras. Útil para conferir listagens.

Slide 18: prefixo e sufixo

Com $w=\text{1011001110001010}$:

• Prefixo: qualquer sequência inicial: 1, 10, 101, 1011, …
• Sufixo: qualquer sequência final: 0, 10, 010, 1010, …

O que os livros dizem (confirmado)

Nos dois livros, $\epsilon$ e a própria $w$ também contam como prefixo e sufixo de $w$. O Menezes lista os prefixos de abcb como $\epsilon$, a, ab, abc, abcb (Exemplo 18, p. 22). O Ramos chama de prefixo próprio (ou sufixo próprio) aquele que é diferente da palavra inteira (p. 79). Os dois também definem subpalavra (ou subcadeia): qualquer trecho contíguo. Todo prefixo e todo sufixo é uma subpalavra.

Slide 19: concatenação

Justapor duas palavras: com $w=\text{abbabbaa}$ e $u=\text{bbaabaab}$, $wu=\text{abbabbaabbaabaab}$.

Propriedades:

• Elemento neutro: $\epsilon w=w\epsilon =w$.
• Associatividade: $w(uv)=(wu)v=wuv$.
• Não é comutativa em geral: $wu\ne uw$ (teste com ab e ba).

Slide 20: concatenação sucessiva (potência)

$w^n$ = $w$ concatenada consigo mesma $n$ vezes. Com $u=\text{bba}$: $u^4=\text{bbabbabbabba}$.

• $w^0=\epsilon$
• $w^n=w{w}^{n-1}=w^{n-1}w$ para $n>0$ (definição recursiva, o mesmo padrão que aparece em potência de relações).

Slide 21: linguagem

Linguagem é qualquer conjunto de sentenças sobre um alfabeto.

Atenção à notação do slide 21

O slide escreve ”$L\in V^{\ast }$ é finita”. O correto é $L\subseteq V^{\ast }$ (uma linguagem é um subconjunto de $V^{\ast }$, não um elemento dele). Além disso, a linguagem não precisa ser finita: $\{0^n{1}^n\mid n>0\}$ é infinita e aparece na própria aula de gramáticas. Provavelmente é um erro de digitação; vale confirmar com o professor.

Os livros confirmam: o Menezes define linguagem formal como “um conjunto de palavras sobre um alfabeto” (Definição 1.24, p. 22) e dá como exemplo a linguagem dos palíndromos, que é infinita. O Ramos diz que uma linguagem pode ser finita ou infinita e que toda linguagem sobre $\Sigma$ é um subconjunto de ${\Sigma }^{\ast }$ (p. 79 e 82).

---

Autoavaliação

1. Quantas palavras de tamanho 3 existem sobre $\{a,b,c\}$?

$3^3=27$.

2. Qual a diferença entre $\varnothing$, $\{\epsilon \}$ e $\epsilon$?

$\epsilon$ é uma palavra (a vazia). $\{\epsilon \}$ é uma linguagem com uma palavra. $\varnothing$ é a linguagem vazia, sem nenhuma palavra.

3. Autômato é reconhecedor ou gerador? E gramática?

Autômato: reconhecedor (formalismo operacional). Gramática: gerador (axiomático). Expressão regular: gerador (denotacional).

4. Se $w=\text{ab}$, quanto vale $w^3$ e $|w^3|$?

$w^3=\text{ababab}$ e $|w^3|=6$. Em geral $|w^n|=n\cdot |w|$.

---

Aprofundamento com os livros

De onde vêm os slides

Lendo os livros, fica claro que os slides desta aula seguem de perto o Menezes (seções 1.1 e 1.5): o trecho sobre sintaxe e semântica, os três tipos de formalismo e até os exemplos de aplicação aparecem quase na mesma ordem nas p. 1 a 4. Então o Menezes é a leitura mais direta para esta aula, e o Ramos serve para ver o mesmo assunto com mais rigor.

Os números de página são das edições que você colocou na pasta: Menezes 3ª edição (Sagra Luzzatto, 2000) e Ramos, José Neto e Vega (Bookman). A 6ª edição do Menezes pode ter paginação diferente.

Onde os livros discordam (vale saber para não se confundir)

Ponto	Slides	Menezes	Ramos
Nome do alfabeto	$V$	$\Sigma$	$\Sigma$
Alfabeto pode ser vazio?	não diz	sim, $\varnothing$ também é alfabeto (p. 21)	não, alfabeto é finito e não vazio (p. 77)
Nome da sequência	sentença	palavra, cadeia ou sentença	cadeia; vira “sentença” quando pertence à linguagem
$w^0$	$\epsilon$	$\epsilon$ se $w\ne \epsilon$; indefinida para ${\epsilon }^0$ (p. 23)	$\epsilon$ sempre (p. 79)
Prefixo inclui $\epsilon$ e $w$?	não diz	sim	sim, e define prefixo próprio

A diferença de ${\epsilon }^0$ é um detalhe curioso do Menezes: como ${\epsilon }^n=\epsilon$ para todo $n>0$, ele prefere deixar ${\epsilon }^0$ sem definição. Na prática quase nunca aparece.

ε, ∅ e {ε}: a confusão mais comum

O Ramos dedica um parágrafo só a isso (p. 80):

Objeto	O que é	Tamanho
$\epsilon$	uma cadeia (a vazia)	$|\epsilon |=0$
$\varnothing$	uma linguagem sem nenhuma cadeia	$|\varnothing |=0$ cadeias
$\{\epsilon \}$	uma linguagem com exatamente uma cadeia	$|\{\epsilon \}|=1$ cadeia

O Menezes reforça no Exemplo 19 (p. 22): $\varnothing$ e $\{\epsilon \}$ são linguagens diferentes.

Operações sobre cadeias e linguagens que os livros acrescentam

• Reverso (Ramos p. 79): $w^R$ é $w$ de trás para frente. Exemplo: $(123abc{)}^R=cba321$ e ${\epsilon }^R=\epsilon$. Um palíndromo é uma palavra com $w=w^R$.
• Concatenação de linguagens (Ramos p. 80): $XY=\{xy\mid x\in X,y\in Y\}$.
• Potências do alfabeto (Ramos p. 81): ${\Sigma }^0=\{\epsilon \}$, ${\Sigma }^1=\Sigma$, ${\Sigma }^2$ = todas as cadeias de tamanho 2, e assim por diante. Então ${\Sigma }^{\ast }={\Sigma }^0\cup {\Sigma }^1\cup {\Sigma }^2\cup \dots$ e ${\Sigma }^{+}={\Sigma }^1\cup {\Sigma }^2\cup \dots$
• Cuidado com $L^{+}$ (Ramos p. 83): para um alfabeto, ${\Sigma }^{+}={\Sigma }^{\ast }-\{\epsilon \}$. Mas para uma linguagem $L$ qualquer, $L^{+}=L^{\ast }-\{\epsilon \}$ só vale se $\epsilon \notin L$. Se $\epsilon \in L$, então $L^{+}=L^{\ast }$.
• Todas as linguagens sobre $\Sigma$ formam o conjunto $2^{{\Sigma }^{\ast }}$ (Ramos p. 83). A menor linguagem é $\varnothing$ e a maior é ${\Sigma }^{\ast }$.
• Complemento de uma linguagem: $\overline{X}={\Sigma }^{\ast }-X$ (Ramos p. 83).

A concatenação não é "fechada" numa linguagem (Menezes, Exemplo 20, p. 23)

Pegue $L$ = palíndromos sobre $\{a,b\}$. aba e bbb estão em $L$, mas ababbb não é palíndromo. Ou seja: concatenar duas palavras de uma linguagem pode gerar uma palavra que está fora dela.

Três jeitos de especificar uma linguagem (Ramos, p. 89)

1. Gramáticas: geram todas as cadeias da linguagem e nenhuma outra. Servem para linguagens finitas e infinitas.
2. Reconhecedores: aceitam toda cadeia da linguagem e rejeitam as demais. Também servem para finitas e infinitas.
3. Enumeração: listar todas as cadeias. Só funciona para linguagens finitas e pequenas.

Uma gramática e um reconhecedor são equivalentes quando toda cadeia gerada pela gramática é aceita pelo reconhecedor e toda cadeia aceita é gerada. O Ramos mostra um contraexemplo (Exemplo 2.20, p. 89): uma gramática que gera “começa com a” e um reconhecedor que aceita “começa com a e termina com b”. A cadeia aba é gerada mas não é aceita, então não são equivalentes.

O reconhecedor genérico (Ramos, seção 2.5, p. 96 a 105)

Todo reconhecedor da disciplina é um caso particular de um modelo com quatro partes: fita de entrada, cursor, máquina de estados (finita) e uma memória auxiliar opcional. O que muda de um tipo para outro:

Reconhecedor	Memória auxiliar	Cursor	Classe (ver 03 - Gramáticas Regulares)
Autômato finito	nenhuma	só lê, só anda para a direita	regulares
Autômato de pilha	uma pilha	só lê, só anda para a direita	livres de contexto
Máquina de Turing com fita limitada	a própria fita, limitada ao tamanho da entrada	lê e escreve, anda nos dois sentidos	sensíveis ao contexto
Máquina de Turing	a própria fita, sem limite	lê e escreve, anda nos dois sentidos	recursivamente enumeráveis

Determinismo como threads

O Ramos usa uma analogia boa para quem programa (p. 99 e 100): quando um autômato não determinístico tem várias opções, imagine que ele cria uma thread para cada opção. A cadeia é aceita se alguma thread chega a uma configuração final. Um autômato determinístico é um programa de uma thread só. Isso prepara o terreno para a aula 05.

Exercícios extras (Menezes, seção 1.6, p. 27)

Exercício 1.1: qual a relação entre linguagens formais e as análises léxica, sintática e semântica?

Resposta minha, com base nas p. 2 a 4 do Menezes: a análise léxica usa linguagens regulares (autômatos finitos e expressões regulares) para reconhecer as unidades básicas, como números e identificadores. A análise sintática usa linguagens livres de contexto (gramáticas e autômatos de pilha) para reconhecer a estrutura do programa. A semântica fica em grande parte fora do alcance das linguagens formais; o próprio Menezes (cap. 5, p. 154 e 155) cita a ligação entre declaração e uso de variáveis como algo que nem as livres de contexto conseguem expressar.

Exercício extra: $\varnothing$, $\{\epsilon \}$ e ${\Sigma }^{\ast }$ são linguagens sobre $\Sigma =\{a,b\}$? Qual é a maior e qual é a menor?

As três são linguagens (todas são subconjuntos de ${\Sigma }^{\ast }$). A menor é $\varnothing$, a maior é ${\Sigma }^{\ast }$. $\{\epsilon \}$ fica no meio, com uma cadeia.

Para aprofundar nos livros

Onde ler (páginas das edições da sua pasta)

• Menezes (3ª ed.): 1.1 Introdução, p. 1 a 4 (base direta dos slides); 1.5 Alfabetos, Palavras, Linguagens e Gramáticas, p. 21 a 26; exercícios 1.1 e 1.19 a 1.21, p. 27 a 30.
• Ramos, José Neto e Vega: 2.1 Símbolos e Cadeias, p. 77; 2.2 Linguagens, p. 79 a 90; 2.5 Reconhecedores, p. 96 a 105.

Relacionadas: Glossário · Flashcards · Referências - Livros