College Online
0%

Linguagens Formais e Automatos

Modulo 1 · Aula 2 ~25 min de leitura Nivel: Introdutorio

Video da aula estara disponivel em breve

Linguagens Formais

Uma linguagem formal e um conjunto (potencialmente infinito) de strings formadas a partir de um alfabeto (conjunto finito de simbolos). As linguagens de programacao sao linguagens formais — cada programa valido e uma string que pertence a linguagem definida pela gramatica da linguagem.

Formalmente: dado um alfabeto Σ, uma linguagem L e um subconjunto de Σ* (todas as strings possiveis sobre Σ).

Python 
# Exemplo: linguagem dos identificadores validos em Python
# Alfabeto: letras + digitos + underscore
# Regra: comeca com letra ou _, seguido de letras, digitos ou _

import re

# Expressao regular que define a linguagem dos identificadores
pattern = r'^[a-zA-Z_][a-zA-Z0-9_]*$'

# Estas strings pertencem a linguagem:
assert re.match(pattern, "resultado")
assert re.match(pattern, "_privado")
assert re.match(pattern, "var2")

# Estas NAO pertencem:
assert not re.match(pattern, "2var")      # comeca com digito
assert not re.match(pattern, "minha-var")  # contem hifen

Hierarquia de Chomsky

Noam Chomsky classificou as linguagens formais em quatro tipos, cada um mais poderoso (e mais custoso de reconhecer) que o anterior:

Diagrama 
+---------------------------------------------------+
|  Tipo 0: Recursivamente Enumeraveis               |
|  Reconhecedor: Maquina de Turing                   |
|  +---------------------------------------------+  |
|  |  Tipo 1: Sensiveis ao Contexto              |  |
|  |  Reconhecedor: Automato Linearmente Limitado |  |
|  |  +---------------------------------------+  |  |
|  |  |  Tipo 2: Livres de Contexto           |  |  |
|  |  |  Reconhecedor: Automato de Pilha (PDA) |  |  |
|  |  |  +--------------------------------+   |  |  |
|  |  |  |  Tipo 3: Regulares             |   |  |  |
|  |  |  |  Reconhecedor: Automato Finito  |   |  |  |
|  |  |  |  (DFA / NFA)                   |   |  |  |
|  |  |  +--------------------------------+   |  |  |
|  |  +---------------------------------------+  |  |
|  +---------------------------------------------+  |
+---------------------------------------------------+

Para compiladores, os dois tipos mais importantes sao:
- Tipo 3 (Regulares): usadas na analise LEXICA (tokens)
- Tipo 2 (Livres de Contexto): usadas na analise SINTATICA (estrutura)
i
Por que isso importa para compiladores? A hierarquia de Chomsky nao e apenas teoria — ela define quais algoritmos voce pode usar para cada parte do compilador. Tokens (identificadores, numeros, operadores) sao linguagens regulares e podem ser reconhecidos por automatos finitos (rapidos, O(n)). A estrutura sintatica de um programa e uma linguagem livre de contexto e precisa de um automato de pilha (parsers). Tentar usar regex para parsear HTML e um erro classico: HTML nao e uma linguagem regular.

Automatos Finitos Deterministicos (DFA)

Um DFA e uma maquina com um numero finito de estados que lê uma string simbolo por simbolo e decide se ela pertence a linguagem. Cada estado tem exatamente uma transicao para cada simbolo possivel.

Diagrama 
DFA que reconhece numeros inteiros (um ou mais digitos):

              digito             digito
         +----------+      +----------+
         |          v      |          v
---> ( q0 ) ---digito---> (( q1 )) --+
      inicio               aceita

q0 = estado inicial (nenhum digito lido)
q1 = estado de aceitacao (pelo menos um digito lido)

Transicoes:
  q0 --[0-9]--> q1
  q1 --[0-9]--> q1
  q0 --[outro]--> ERRO
  q1 --[outro]--> ERRO (para o DFA; na pratica, retorna o token)
Python 
# Implementacao de um DFA em Python

class DFA:
    def __init__(self, states, alphabet, transitions, start, accept):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions  # dict: (estado, simbolo) -> estado
        self.start = start
        self.accept = accept

    def accepts(self, input_string):
        current = self.start
        for symbol in input_string:
            if symbol not in self.alphabet:
                return False
            key = (current, symbol)
            if key not in self.transitions:
                return False
            current = self.transitions[key]
        return current in self.accept

# DFA para numeros inteiros
digits = set('0123456789')
transitions = {}
for d in digits:
    transitions[('q0', d)] = 'q1'
    transitions[('q1', d)] = 'q1'

dfa = DFA(
    states={'q0', 'q1'},
    alphabet=digits,
    transitions=transitions,
    start='q0',
    accept={'q1'}
)

print(dfa.accepts("42"))     # True
print(dfa.accepts("0"))      # True
print(dfa.accepts(""))       # False (nenhum digito)
print(dfa.accepts("12a3"))   # False ('a' nao esta no alfabeto)

Automatos Finitos Nao-Deterministicos (NFA)

Um NFA e como um DFA, mas permite multiplas transicoes para o mesmo simbolo e transicoes vazias (epsilon, ε). Um NFA aceita se algum caminho possivel leva a um estado de aceitacao.

Diagrama 
NFA que reconhece strings terminando em "ab":

              a,b              a               b
         +----------+    +----------+    +----------+
         |          v    |          v    |          v
---> ( q0 ) ----a----> ( q1 ) ---b----> (( q2 ))
      inicio                              aceita

q0 pode ir para q0 (com 'a' ou 'b') OU para q1 (com 'a')
Isso e o nao-determinismo: dois caminhos possiveis com 'a' em q0
*
Equivalencia NFA = DFA Para toda NFA, existe um DFA equivalente (que reconhece a mesma linguagem). A conversao usa a construcao de subconjuntos (subset construction): cada estado do DFA resultante e um conjunto de estados do NFA. Na pratica, ferramentas como flex convertem regex para NFA, depois para DFA, para gerar lexers eficientes.

De Regex para Automatos

Expressoes regulares e automatos finitos sao equivalentes em poder: toda regex pode ser convertida para um NFA (construcao de Thompson), e todo NFA pode ser convertido para um DFA (construcao de subconjuntos).

Diagrama 
Regex  ----Thompson----> NFA ----Subconjuntos----> DFA ----Minimizacao----> DFA minimo

Exemplo: regex  a(b|c)*

Passo 1 - NFA (Thompson):
                  +--b--+
                  |      |
---> (q0) --a--> (q1) --+--> (q1)    [loop em b|c]
                  |      |
                  +--c--+

(q1) e de aceitacao

Passo 2 - DFA equivalente:
                b        b
              +---+    +---+
              v   |    v   |
---> (q0) --a--> (q1) ----+
              aceita   c  c
              +---+    +---+
              v   |
              (q1)

No harness.os

O formato CLAUDE.md e os arquivos de regras do harness.os sao definidos por gramaticas implicitas. Os triggers de regras usam padroes que seguem expressoes regulares:

YAML 
# Exemplo de regra harness.os com trigger baseado em padroes
title: Commit Hygiene
context: git-commit
trigger: "quando o usuario pede um commit"
content: |
  Nao adicionar Co-Authored-By: Claude
  Usar mensagens concisas e descritivas

# O frontmatter YAML tem uma gramatica definida:
# regra    ::= frontmatter corpo
# frontmatter ::= '---' NEWLINE campos '---' NEWLINE
# campos   ::= campo (NEWLINE campo)*
# campo    ::= CHAVE ':' ESPACO VALOR
# corpo    ::= TEXTO_LIVRE

A gramatica do frontmatter YAML e regular (pode ser reconhecida por um automato finito), mas o corpo do arquivo CLAUDE.md usa Markdown, que contem estruturas livres de contexto (como listas aninhadas e blocos de codigo). Entender a hierarquia de Chomsky ajuda a escolher a ferramenta certa para parsear cada parte.

Resumo

Exercicio

Escreva a gramatica (em notacao BNF) para o frontmatter de um arquivo de regra do harness.os. A gramatica deve aceitar os campos title, context, trigger, e content, delimitados por ---. Depois, desenhe o DFA que reconhece a delimitacao do frontmatter (a sequencia --- seguida de newline).

Verifique seu entendimento

Na hierarquia de Chomsky, qual tipo de linguagem e reconhecido por automatos finitos (DFA/NFA)?

  • Tipo 0 — Recursivamente enumeraveis
  • Tipo 1 — Sensiveis ao contexto
  • Tipo 2 — Livres de contexto
  • Tipo 3 — Regulares