Aula 14 Gramáticas e Máquina de Turing

Prévia do material em texto

Aula 14 – Gramáticas e Máquina de Turing 
1. As principais características da máquina de Turing são: 
I. A máquina de Turing tem uma fita que é ilimitada em ambas as direções, permitindo 
qualquer número de movimentos para a esquerda e para a direita. 
II. A máquina de Turing é determinística no sentido de que δ define no máximo um 
movimento para cada configuração. 
III. Não há nenhum arquivo de entrada especial. Presume-se que no momento inicial a 
fita tenha algum conteúdo específico. Parte disso pode ser considerada uma entrada. 
IV. Não há dispositivo de saída especial. Sempre que a máquina para, parte ou todo o 
conteúdo da fita pode ser visto como saída. 
Quais alternativas estão corretas? 
 
A. Apenas as alternativas I e II estão corretas. 
B. Apenas as alternativas I, II e III estão corretas. 
C. Apenas as alternativas III e IV estão corretas. 
D. Apenas as alternativas IV e V estão corretas. 
E. As alternativas I, II, III e IV estão corretas. 
 
2. Considere a gramática irrestrita sobre o alfabeto Σ = {a}, tendo o S como símbolo 
inicial e com as seguintes derivações: 
S → AS | aT 
Aa → aaaA 
AT → T 
T → ε 
Qual alternativa mostra uma derivação de a9 usando a gramática irrestrita? E qual é a 
linguagem gerada por essa gramática irrestrita? 
 
A. S ⇒ AS ⇒ AAS ⇒ AAaT ⇒ AaaaAT ⇒ AaaaT ⇒ aaaAaaT ⇒ aaaaaaAaT ⇒ 
aaaaaaaaaAT ⇒ aaaaaaaaaT ⇒ aaaaaaaaa. A linguagem é L(S) = {a3n | n ≥ 0}. 
 
B. S ⇒ AS ⇒ aAAS ⇒ AAaT ⇒ AaaaAT ⇒ AaaaT ⇒ aaaAaaT ⇒ aaaaaaAaT ⇒ 
aaaaaaaaaAT ⇒ aaaaaaaaaT ⇒ aaaaaaaaa. A linguagem é L(S) = {a | n ≥ 0}. 
 
C. S ⇒ AS ⇒ aaAAS ⇒ AAaT ⇒ AaaaAT ⇒ AaaaT ⇒ aaaAaaT ⇒ aaaaaaAaT ⇒ 
aaaaaaaaaAT ⇒ aaaaaaaaaT ⇒ aaaaaaaaa. A linguagem é L(S) = {a1 | n ≥ 0}. 
 
D. S ⇒ AS ⇒ AAS ⇒ aAAaT ⇒ AaaaAT ⇒ AaaaT ⇒ aaaAaaT ⇒ aaaaaaAaT ⇒ 
aaaaaaaaaAT ⇒ aaaaaaaaaT ⇒ aaaaaaaaa. A linguagem é L(S) = {a0 | n ≥ 0}. 
 
E. S ⇒ AS ⇒ AAS ⇒ AAaT ⇒ aAaaaAT ⇒ AaaaT ⇒ aaaAaaT ⇒ aaaaaaAaT ⇒ 
aaaaaaaaaAT ⇒ aaaaaaaaaT ⇒ aaaaaaaaa. A linguagem é L(S) = {a0n | n ≥ 0}. 
 
 
 
3. Pode ser mostrado que gramáticas irrestritas caracterizam um tipo de linguagem. Isso 
é o mesmo que dizer que para toda gramática irrestrita G existe alguma máquina de 
Turing capaz de reconhecer L(G), e vice-versa. 
De acordo com a hierarquia de Chomsky, que linguagem pode ser caracterizada pela 
gramática irrestrita? 
 
A. Sensível ao contexto. 
B. Livre de contexto. 
C. Regular. 
D. Recursiva. 
E. Recursivamente enumerável. 
 
4. Considere a seguinte gramática descrita: 
G = ({S,X},{x,y},P, S) 
e seus passos de derivação: 
S → SXSy, 
XS → y, 
X → SXS, 
S → yxx 
Que tipo de gramática é representado por G? 
 
A. Gramática livre de contexto 
B. Gramática sensível ao contexto. 
C. Gramática do tipo 1. 
D. Gramática do tipo 2. 
E. Gramática irrestrita. 
 
5. Considere a seguinte gramática descrita: 
G = ({S,X},{x,y},S,P) 
e seus passos de derivação: 
S → SyS, 
S → XX, 
S → yxy, 
X → ySy, 
X → ε 
Que tipo de gramática é representado por G? 
 
A. Gramática livre de contexto. 
B. Gramática irrestrita. 
C. Gramática do tipo 1. 
D. Gramática sensível ao contexto. 
E. Gramática regular.