Question

Seja a seguinte gramática ; ; ; ; ; ; ; . Esta gramática é sensível ao contexto e, portanto, a linguagem que ela gera é uma linguagem sensível ao contexto. Uma alternativa para descrever linguagens é através de sua apresentação como um conjunto em linguagem matemática.

Com relação a gramática acima e a linguagem gerada por ela, assinale a representação em conjunto que descreve a linguagem gerada pela gramática.

Escolha uma:
a.
b.
c.
d. Incorreto
e.
Questão 2
Incorreto
Atingiu 0,00 de 1,00
Não marcadaMarcar questão
Texto da questão
Considere uma linguagem sensível ao contexto qualquer sobre o alfabeto . Este é o caso que você sabe que existe uma gramática sensível ao contexto que gera , isto é . Seja um conjunto finito de cadeias, tal que, .

Com base no texto e no que você sabe sobre a gramática , que gera , assinale a única alternativa verdadeira sobe qualquer hipótese sobre e .

Escolha uma:
a. A linguagem não é recursiva. Incorreto
b. A linguagem é livre de contexto e é sensível ao contexto.
c. A linguagem não é recursivamente enumerável.
d. Não é possível afirmar nada sobre .
e. A linguagem é regular e também é regular.
Questão 3
Correto
Atingiu 1,00 de 1,00
Não marcadaMarcar questão
Texto da questão
Recordamos que dada uma máquina de Turing, definida pela tupla, , definimos a linguagem reconhecida pela máquina de Turing como:
e M para em
Considere a seguinte máquina de Turing:

Maq. de Turing
Fonte: Os autores

Assinale a alternativa que melhor descreve a linguagem reconhecida pela máquina de Turing do texto base.

Escolha uma:
a. Cadeias que representam números pares escritos na base 2.
b. Cadeias que representam a concatenação de dois números escritos na base 2, cuja a soma é par.
c. Cadeias que representam números ímpares escritos na base 2. Correto
d. Cadeias que representam números pares, cuja representação na base 2 é um palíndromo.
e. Cadeias que representam a concatenação de dois números escritos na base 2, cuja a soma é ímpar.
Questão 4
Incorreto
Atingiu 0,00 de 1,00
Não marcadaMarcar questão
Texto da questão
O teorema de Rice afirma que qualquer que seja a linguagem , o conjunto de máquinas de Turing que reconhece só é recursivo nos casos em que e , onde é o alfabeto de . A ideia é entender como sendo uma propriedade sobre cadeias. E que reconhecer computacionalmente máquinas de Turing que reconhecem estas cadeias não é possível propriedade se não trivial ( e ou ) . Por exemplo, a propriedade " é uma máquina de Turing que não para" é não trivial. Portanto a linguagem não é recursiva. Esta é linguagem das máquinas de Turing que não param.

Existem casos que as propriedades sobre máquinas de Turing, isto é , não são sobre as linguagens que estas reconhecem e não é possível aplicar o teorema de Rice nestes casos. Indique a alternativa abaixo onde isso acontece. Considere uma máquina de Turing arbitrária e a propriedade descrita na alternativa.

Escolha uma:
a. aceita uma linguagem regular. Incorreto
b. tem a mesma quantidade de estados que uma máquina que aceita a linguagem das cadeias com número par de símbolos.
c. só aceita cadeias na forma , com .
d. aceita a linguagem dos grafos fortemente conexos.
e. aceita uma linguagem recursivamente enumerável.
Questão 5
Correto
Atingiu 1,00 de 1,00
Não marcadaMarcar questão
Texto da questão
Seja a máquina de Turing , definida como ; ; . Para toda máquina de Turing pode-se associar duas linguagens relacionadas às suas computações. Uma linguagem é o conjunto das cadeias para as quais a máquina para, para em um estado qualquer , outra é para com escrita na fita.

Com relação aos dois conjuntos descritos no texto, associados à máquina de Turing definida no texto, assinale.

Escolha uma:
a. e
b. e
c. e Correto
d. e
e. e

Answer 1

SEGUE IMAGENS ACERTEI +2

Answer 2

:::::::::::::respostas :::::::::::::::::