Módulo 01: Fundamentos da Computação • Ciência da Computação Formal

🗺️ 1. Hierarquia de Chomsky e Poder Computacional

flowchart TD
    subgraph CHOMSKY["Hierarquia de Linguagens e Autômatos"]
        T0["Tipo 0: Irrestrita / Recursivamente Enumerável
(Máquina de Turing)"]
        T1["Tipo 1: Sensível ao Contexto
(Autômato Linearmente Limitado)"]
        T2["Tipo 2: Livre de Contexto
(Autômato com Pilha - PDA)"]
        T3["Tipo 3: Regular
(Autômato Finito Determinístico - DFA/NFA)"]
        
        T0 --- T1
        T1 --- T2
        T2 --- T3
    end

    style T0 fill:#ffebee,stroke:#f44336,stroke-width:2px
    style T1 fill:#fff3e0,stroke:#ff9800,stroke-width:2px
    style T2 fill:#ede7f6,stroke:#7e57c2,stroke-width:2px
    style T3 fill:#e8f5e9,stroke:#4caf50,stroke-width:2px

🏛️ 2. Fundamentação Teórica

A Teoria da Computação investiga os limites matemáticos do que pode ser resolvido por máquinas de processamento de símbolos.

2.1 Autômatos Finitos Determinísticos (DFA)

Um DFA é formalmente definido como uma 5-tupla: \(M = (Q, \Sigma, \delta, q_0, F)\)

Onde:

  • $Q$: Conjunto finito de estados.
  • $\Sigma$: Alfabeto de símbolos de entrada.
  • $\delta$: Função de transição $\delta: Q \times \Sigma \to Q$.
  • $q_0 \in Q$: Estado inicial.
  • $F \subseteq Q$: Conjunto de estados finais ou de aceitação.

2.2 A Máquina de Turing (Alan Turing, 1936)

A Máquina de Turing é o modelo matemático canônico de um computador universal de uso geral: \(M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})\)

  • $\Gamma$: Alfabeto da fita ($\Sigma \subset \Gamma$, contendo o símbolo branco $\sqcup$).
  • $\delta$: Função de transição $\delta: Q \times \Gamma \to Q \times \Gamma \times {L, R}$.

2.3 A Tese de Church-Turing e o Problema da Parada (Halting Problem)

A Tese de Church-Turing postula que qualquer cálculo algoritmicamente concebível pode ser simulado por uma Máquina de Turing.

Alan Turing provou a existência de problemas indecidíveis (insolúveis por qualquer algoritmo). O clássico Problema da Parada demonstra que é logicamente impossível criar um algoritmo $H(P, I)$ que determine infalivelmente se qualquer programa $P$ executando sobre uma entrada $I$ irá terminar ou entrar em loop infinito.

💻 3. Simulação Computacional de Autômato Finito (DFA)

class DFA:
    """Emulador formal de Autômato Finito Determinístico."""
    def __init__(self, states: set, alphabet: set, transitions: dict, start_state: str, accept_states: set):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.accept_states = accept_states

    def process(self, string: str) -> bool:
        current = self.start_state
        for char in string:
            if char not in self.alphabet:
                return False
            current = self.transitions.get((current, char))
            if current is None:
                return False
        return current in self.accept_states

# Reconhece strings binárias com número PAR de '1's
dfa_paridade = DFA(
    states={'q_par', 'q_impar'},
    alphabet={'0', '1'},
    transitions={
        ('q_par', '0'): 'q_par',
        ('q_par', '1'): 'q_impar',
        ('q_impar', '0'): 'q_impar',
        ('q_impar', '1'): 'q_par'
    },
    start_state='q_par',
    accept_states={'q_par'}
)

if __name__ == "__main__":
    testes = ["1010", "111", "000", "11011", "1011"]
    print("=== SIMULAÇÃO DE AUTÔMATO FINITO (PARIDADE DE BITS) ===")
    for t in testes:
        valido = dfa_paridade.process(t)
        print(f"Cadeia '{t}': {'[ACEITA - Par de 1s]' if valido else '[REJEITADA - Ímpar de 1s]'}")