TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

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

Por:   •  30/5/2020  •  Trabalho acadêmico  •  546 Palavras (3 Páginas)  •  413 Visualizações

Página 1 de 3

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.

...

Baixar como (para membros premium)  txt (3.8 Kb)   pdf (54.8 Kb)   docx (8.3 Kb)  
Continuar por mais 2 páginas »
Disponível apenas no TrabalhosGratuitos.com