Questões Disciplina Online - Aspectos Teóricos da Computação

1. A Hierarquia de Chomsky prevê quatro tipos de Linguagens, que são denominadas respectivamente:

R: Alternativa C

Regular – São geradas pelas gramáticas regulares e são reconhecidas por autômatos finitos.

Livre de Contexto – São geradas pelas gramáticas livres de contexto e reconhecidas por autômatos de pilha.

Dependente de Contexto – Gerada pela gramática sensível a contexto e irrestrita. São processadas pela Máquina de Turing.

Irrestrita – Nenhum tipo de limitação é imposta. A gramática irrestrita pode gerar linguagens recursivamente enumeráveis.

2. A configuração de uma Máquina de Turing é indicada por uma tripla, constituída dos seguintes elementos:

R: Alternativa C

A porção do conteúdo da fita de trabalho que se encontra à esquerda do cursor de acesso, porção do conteúdo da fita de trabalho que se encontra à direita do cursor de acesso, incluindo a posição correntemente apontada por ele e o estado corrente.

3. Considere as seguintes afirmações sobre autômatos finitos e expressões regulares:

I - A classe das linguagens aceita por um Autômato Finito Determinístico (AFD) não é a mesma que um Autômato Finito Não Determinístico (AFND).

II - Para algumas expressões regulares não é possível construir um AFD.

III - A expressão regular (b+ba)+ aceita os "strings" de b's e a's começando com b e não tendo dois a's consecutivos.

Selecione a alternativa correta.

R: Alternativa C

III – Seguindo as regras dos autômatos finitos e expressões regulares, o String mencionado na afirmativa III está correto. Deve-se lembrar da seguinte regra:

Quando, por exemplo, há a* (asterisco), significa que pode haver a, mais de uma vez, ou não. Já no caso de a+, significa que, obrigatoriamente deve ter pelo menos um a, e caso esteja no início da string, ela obrigatoriamente deverá começar com a.

4. Uma Linguagem aceita por uma Máquina de Turing é dita:

R: Alternativa A

Uma linguagem aceita pela Máquina de Turing é dita recursivamente enumerável. Essa linguagem é gerada pela gramática sensível a contexto e irrestrita. Para o processamento das linguagens dependentes de contexto, a MT com fita de entrada limitada é suficiente, enquanto que para linguagens irrestritas a MT deve se apresentar de acordo com a sua definição original (fita de entrada ilimitada à direita).

5. Assinale a alternativa que apresenta uma máquina conceitual capaz de reconhecer apenas a componente regular das Linguagens previstas na Hierarquia de Chomsky.

R: Alternativa A

Uma máquina de estados finitos pode ser classificada como uma máquina abstrata que deve estar em um de seus finitos estados, portanto, a máquina está em apenas um estado por vez, e um estado armazena as informações desde a entrada de um estado até o momento atual.  

6. Analise as seguintes afirmativas.

I. Todo autômato finito não-determinístico pode ser simulado por um autômato finito determinístico.

II. Todo autômato finito determinístico pode ser simulado por um autômato finito não determinístico.

...