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)
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.
Considerando-se a definição autômatos finitos, assinale a única alternativa que contém somente cadeias de caracteres totalmente aceitas pelo autômato finito da figura.
- A AB, ABAB, ABABAB
- B AB, ABBA, ABABAB
- C AB, ABAA, ABABAB
- D AB, ABAB, ABBAAB
- E AB, ABAB, ABAABA
Leia os itens contendo as expressões regulares que poderão ser associadas ao autômato da figura, conforme aquilo que a bibliografia adotada descreve sobre autômatos finitos e expressões regulares.
I) A expressão regular 0*1(1+00*1)* representa o automato da figura.
II) A expressão regular 0*1*1+11*0*1 representa o automato da figura.
III) A expressão regular (0+1)*1 representa o automato da figura.
Assinale somente a alternativa que apresenta todas as afirmativas CORRETAS.
- A Somente I e II
- B Somente I e III
- C Somente II
- D Somente II e III
- E Somente I