Transdutores
Reconhecedores
Máquina de Moore
Autômatos Finitos
Transdutores
Máquina de Mealy
Máquina de Moore
Uma Máquina de Moore é uma sêxtupla M = (Q, Σ, ∆, δ, σ, i) em
que:
- Q ≡ conjunto de estados
- Σ ≡ alfabeto de entrada
- δ ≡ função de transição (δ : Q × Σ → Q)
- i ≡ estado inicial
- ∆ ≡ alfabeto de saída
- σ ≡ função de saída (σ : Q → ∆)
Função de Saída Estendida de Moore
Seja uma Máq. de Moore M = (Q, Σ, ∆, δ, σ, i), a função de saída
estendida r : Q × Σ* → ∆* é definida como:
- r(q, λ) = σ(q), ∀q ∈ Q
- r(q, ay) = σ(q) r(δ(q, a), y), ∀q ∈ Q, ∀a ∈ Σ, ∀y ∈ Σ*
Representação de uma transição : δ(q, a) = q’
q / σ(q)
a
q’/σ(q’)
Exemplo: Cálculo do resto da divisão por 4
Exercício: Cálculo do núm. de uns nos 2 últimos dígitos de
uma palavra binária
Máquina de Mealy
Uma Máquina de Mealy é uma sêxtupla M = (Q, Σ, ∆, δ, σ, i) em
que:
- Q ≡ conjunto de estados
- Σ ≡ alfabeto de entrada
- δ ≡ função de transição (δ : Q × Σ → Q)
- i ≡ estado inicial
- ∆ ≡ alfabeto de saída
- σ ≡ função de saída (σ : Q × Σ → ∆)
Representação de uma transição : δ(q, a) = q’
q
a/b
q’
σ(q, a) = b
Função de Saída Estendida de Mealy
Seja uma Máq. de Mealy M = (Q, Σ, ∆, δ, σ, i), a função de saída
estendida s : Q × Σ* → ∆* é definida como:
- s(q, λ) = λ, ∀q ∈ Q
- s(q, ay) = σ(q, a) s(δ(q, a), y),∀q ∈ Q,∀a ∈ Σ,∀y ∈ Σ*
Observação : A saída “computada” por uma Máquina de Mealy
para uma palavra w ∈ Σ* é dada por s(i, w).
Exemplo: Cálculo do quociente da divisão por 4
Exercício: Cálculo do quociente da divisão por 6