Dado o autômato Finito abaixo, assinale a alternativa onde a expressão regular (ER) o representa:
- A a*b(cb)a*.
- B aba(cb).
- C a*b(cb)*a.
- D a*b*c*b*a*.
Questões de Autômatos (Algoritmos e Estrutura de Dados)
O autômato finito determinístico
- A corresponde à função de transição que recebe um estado ou um símbolo de entrada que sempre retorna um conjunto de estados como resultado.
- B tem a capacidade de adivinhar algo sobre sua entrada ao testar valores.
- C pode, para cada entrada, transitar a partir do seu estado atual em um e somente um estado.
- D permite zero, uma ou n transições para os estados de entrada.
- E consegue estar em vários estados ao mesmo tempo.
Dada a expressão regular
(^[0-9]$|^9[1-8]?$|^2[0-9]{2}$),
assinale a alternativa que satisfaz essa expressão.
- A 11
- B 912
- C 2324
- D 93847
- E 91
Considere um autômato não determinístico NFA ܰN = (Q, ∑, δ, a, F), onde Q = {a, b, c, d, e, g} representa os estados, ∑ = {0,1} é o alfabeto, δ é a função de transição, ܽa é o estado inicial e F = {c, ƒ} os estados de aceitação, representados pelo diagrama a seguir
A linguagem desse autômato pode ser descrita como
- A {w ∈ ∑*|w contém exatamente dois 1s e pelo menos dois 0s}
- B {w ∈ ∑*|w contém exatamente dois 1s ou exatamente dois 0s}
- C {w ∈ ∑*|w contém exatamente dois 1s ou pelo menos dois 0s}
- D {w ∈ ∑*|w contém pelo menos dois 1s ou exatamente dois 0s}
- E {w ∈ ∑*|w contém pelo menos dois 1s ou pelo menos dois 0s}
Considerando-se a definição sobre autômatos finitos e linguagens, assinale a única alternativa que contém a disposição correta (da esquerda para a direita) dos tipos de gramática segundo o critério da abrangência das linguagens geradas (gramática mencionada gera linguagem que abrange a linguagem gerada pela gramática a sua direita – hierarquia de Chomsky).
- A Gramáticas irrestritas > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas regulares.
- B Gramáticas regulares > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas irrestritas.
- C Gramáticas livres de contexto > Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas regulares.
- D Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas regulares.
- E Gramáticas regulares > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas irrestritas.