Linguagens formais e automatos

Prévia do material em texto

EXERCÍCIOS
UNIT1
1.
Os autômatos, ou máquinas de estados, são abstrações matemáticas para representar
modelos computacionais. Esses modelos computacionais possibilitam a idealização de
computadores, podendo representar linguagens complexas, tais como as recursivas e
recursivamente enumeráveis às simples linguagens regulares. Um dos tipos de
autômatos usados para reconhecer a linguagem regular é o AFD, marcado fortemente por
seu determinismo.
 Assinale a alternativa correta acerca do significado de determinismo usado pelo AFD.
É a capacidade que um autômato finito tem de gerar um único ramo de computação para cada
cadeia de entrada fornecida. Esse autômato pode ser expressado por meio da quíntupla da
formalização.
O determinismo usado no AFD é a capacidade de gerar um único ramo de computação
para cada cadeia fornecida na entrada. É importante salientar que esse autômato é
definido a partir de uma 5-upla da sua formalização. Em um AFD, todos os símbolos do
alfabeto devem ser consumidos obrigatoriamente pela função de transição, podendo
chegar a vários estados de aceitação a partir do único estado inicial permitido no AFD.
Em outras palavras, no AFD podem existir de 1 a N estados finais e necessariamente
apenas 1 estado inicial. É interessante frisar que não existe símbolo espontâneo sendo
determinante no estado de aceitação ou em qualquer outra transição; caso tivesse
transição com o símbolo épsilon, incorreria na aparição do não determinismo do
autômato. No tocante à computação realizada via função programa em um autômato
finito, não há limitação de estados utilizados, mas a quantidade de estados varia em
virtude do autômato utilizado, podendo ter muitos estados, entre estes diversos estados
de aceitação e somente um estado inicial.
2.
O diagrama de estados usado no AFD é um recurso gráfico muito expressivo para
representar muitas máquinas, entre elas as máquinas de estados finitas. Com esse
diagrama, é possível estabelecer a transição de um estado para outro por meio do
consumo dos símbolos disponíveis no alfabeto em questão. A seguir, são informados
detalhes sobre um diagrama de estados:
 Q = ｛q0, q1, q2, q3, q4, q5｝,
Σ = {0, 1},
Função programa = {
δ(q0, 0) = q5, δ(q0, 1) = q1,
δ(q1, 0) = q2, δ(q1, 1) = q5,
δ(q2, 0) = q5, δ(q2, 1) = q3,
δ(q3, 0) = q4, δ(q3, 1) = q5,
δ(q4, 0) = q4, δ(q4, 1) = q4,
δ(q5, 0) = q0, δ(q5, 1) = q0
}
q0 é q0.
F = { q0, q4}
De acordo com as informações, indique qual diagrama corresponde às especificações
descritas.
3. O diagrama de estados usado no AFD é um recurso gráfico muito expressivo para
representar muitas máquinas, entre elas as máquinas de estados finitas. Com esse
diagrama, é possível estabelecer a transição de um estado para outro por meio do
consumo de todos os símbolos disponíveis no alfabeto usado em determinada
linguagem. A seguir, é esboçado o diagrama 2. Determine a linguagem L(M2) aceita pelo
AFD M2 representado no diagrama
L(M2) = ｛w ∈ (0, 1)* | w é formada por uma cadeia que deve ter uma sequência mínima de
cinco 1s consecutivos｝.
Observe alguns exemplos de cadeias aceitas que foram geradas por esse diagrama:
11111, 011111, 0111110, 00111110, 0111111100, e assim por diante. Observe que todas
essas cadeias têm no mínimo cinco 1s seguidos, independentemente de serem
antecedidos ou sucedidos de cadeias alternadas de 0s e 1s. Logo, é correto afirmar que
w é formada por uma cadeia que deve ter uma sequência mínima de cinco 1s
consecutivos, não tendo aparições de 0s entre esses cinco 1s. A cadeia final
processada por esse AFD é aceita independentemente de o comprimento ser ímpar ou
par, mas que tenha os cinco 1s seguidos, embora a menor cadeia aceita seja a 11111,
tendo comprimento ímpar. 
4. A formalização do autômato finito deteminístico (AFD) fornece a precisão e a notação
para representar esse tipo de modelo computacional (AFD). No AFD, sua formalização
pode ser expressada por meio da 5-upla (Q, Σ, δ, q0, F). A seguir, é esboçado o diagrama
que reconhece a linguagem L(M3).
Leia as afirmativas a seguir a respeito dos componentes da formalização do AFD:
I. Esse AFD tem Q = ｛q0, q1, q2, q3, q4｝, F = {q1, q3} e Σ = {p, a, i}.
II. Esse AFD tem Q = {q0, q1, q2, q3, q4}, F = {q3}, δ(q0, a) = q0.
III. Esse AFD tem Q = {q0, q1, q2, q3, q4}, F = {q3}, Σ = {p, i}, q0 = q1.
IV. Esse AFD tem Q = {q0, q1}, F = {q2} e Σ = {p, a, i}, δ(q2, a) = q2, δ(q2, p) = q2.
V. Esse AFD tem Q = {q0, q1, q2, q3, q4}, Σ = {p, a, i}, δ(q0, i) = q0.
Assinale a alternativa que contém as assertivas corretas:
II e V.
Observe que a resolução desse algoritmo fica em torno do preenchimento da 5-upla (Q,
δ, δ, q0, F); portanto, vamos informar a valoração de cada componente. Q = ｛q0, q1,
q2, q3, q4｝ δ = {p, a, i} δ: Q × δ δ Q = { δ(q0, a) = q0, δ(q0, i) = q0, δ(q0, p) = q1, δ(q1,
a) = q2, δ(q1, i) = q4, δ(q1, p) = q4, δ(q2, a) = q4, δ(q2, p) = q1, δ(q2, i) = q3, δ(q3, a) =
q3, δ(q3, p) = q3, δ(q3, i) = q3, δ(q4, a) = q4, δ(q4, p) = q1, δ(q4, i) = q4 } q0 é o q0. F =
{q3}. Logo, as alternativas que usam corretamente as atribuições da formalização do
AFD a partir do diagrama 3 são a II e a V. Note que há atribuições na 5-upla da
formalização do AFD incorretas. É importante atentar aos conjuntos dos estados totais,
finais e do alfabeto da linguagem, assim como a todas as saídas da função de
transição. Ao se referir ao AFD em questão, as informações erradas são: F = {q1, q3}, δ
= {p, i}, q0 = q1, Q = {q0, q1}, F = {q2}, δ(q2, a) = q2, δ(q2, p) = q2. 
5.
Em AFDs, pode haver muitas soluções para o mesmo problema, incluindo aquelas
soluções com muitos estados. Ao implementar um AFD, uma pergunta pertinente que se
deve fazer é se o AFD foi construído com o menor número possível de estados. Com isso,
é apropriada a utilização do algoritmo de minimização de autômatos.
Analise as afirmativas a seguir, que tratam das características do algoritmo de
minimização de autômatos, e classifique-as em verdadeiras (V) ou falsas (F):
( ) Neste algoritmo, os estados finais e os não finais são separados na primeira interação,
depois são unidos, chegando a ser indissolúveis.
( ) Os estados equivalentes são aqueles que, ao consumirem um símbolo, vão ter
comportamentos de aceitação/rejeição idênticos.
( ) O algoritmo procura uma partição, de forma que os estados não equivalentes estejam
no mesmo bloco.
( ) A minimização do autômato finito une os estados equivalentes entre si, alterando e
aperfeiçoando o funcionamento do autômato.
Assinale a alternativa que apresenta a ordem correta:
Você acertou!
B.
F, V, F, F.
Ao realizar a minimização de AFD, deve-se ter em mente que nem sempre uma única
interação pode encontrar a melhor minimização possível; logo, dependendo da
quantidade de estados do autômato, muitas interações vão acontecer, não sendo esse
conjunto de estados (aceitação e não aceitação) indissolúvel somente na primeira
interação, a não ser que haja apenas uma interação na minimização. Em cada
interação, os estados de aceitação e não aceitação são separados em uma partição Z0
= ｛F, Q – F｝ e, ao final da interação, são unidos, repetindo esse processo em toda a
interação.
Ao estabelecer a equivalência entre os estados X e X’, por definição, se dois estados X
e X’ têm equivalência, então o resultado final (aceitação ou rejeição) do processamento
de qualquer cadeia w δ δ* deve ser igual se iniciado a partir de X ou a partir de X. Isso
incorre que X e X’ vão se comportar de forma idêntica. A minimização de AFD diminui a
quantidade de estados, não alterando o funcionando do AFD, porém o torna menor no
tocante à quantidade de estados usados inicialmente.
1.
Uma cadeia de entrada a1a2 ...an é aceita/reconhecida por um AFND se existe AO MENOS
UMA sequência de transições que leva do estado inicial para algum estado final.
Nesse contexto, sobre os AFND, assinale a alternativa correta.
Você acertou!
B.
Um AFND tem uma cadeia aceita se, pelo menos, um estado final é atingido ao final do
processamento, lembrando que o autômato pode ter mais de um estado final.O AFND (ou AFN) pode ter mais de um estado final, e sua aceitação pode ser feita se
pelo menos um deles for atingido. Além disso, pode realizar mais de uma transição para
o mesmo símbolo de entrada, não se limitando apenas a determinada transição.
O poder de expressão não difere, uma vez que AFDs são subconjuntos de AFNs, e a
transição vazia não impede a conversão de AFN para AFD. O funcionamento do AFN
possibilita mais de uma transição a um símbolo de entrada em um mesmo estado.
2. As tabelas AFN ajudam a ter uma visão de cada transição com base no estado atual,
símbolo de entrada e estado(s) alvo(s).
Observe o diagrama AFN a seguir:
 Assinale a alternativa que apresenta corretamente a tabela AFN correspondente ao AFN.
3. A definição formal de um AFN é composta basicamente de uma 5-upla, cuja notação
pode ser dada por:
M=(Ʃ, Q, δ,q0,F)
Em que Ʃé o alfabeto, Q o conjunto de estados, q0 o estado inicial e F o conjunto de
estados finais.
Considere o seguinte AFN, em que:
 Ʃ = (a, b);
F = ｛q2｝.
Analise as afirmativas:
I. O AFN tem transições vazias para q2.
II. O AFN em questão aceita todas as cadeias iniciadas por a ou b.
III. O AFN em questão termina, necessariamente, com dois símbolos iguais.
IV. O AFN aceita cadeias de, no mínimo, dois caracteres.
É correto o que se afirma nos itens:
Resposta correta.
B.
III e IV, apenas.
Observe que em q0 há um loop para os símbolos a e b. Pelo não determinismo, há
transição para o estado q1 (caso a) ou q3 (caso b). Partindo-se de q1, a única transição
é a partir da chegada de outro a. Partindo-se de q3, a única transição é pela chegada
de outro b. Ambas finalizam no estado q2, que não tem nenhuma transição, invalidando
o item I. Além disso, o AFN sempre deverá terminar em aa ou bb, validando o item III.
Ainda que possa aceitar qualquer quantidade de a ou b no início, a transição mínima é
aceitar pelo menos aa ou bb, validando o item IV. Porém, dada a obrigatoriedade
instituída em (III), o item II torna-se errado, pois não se aceitam todas as cadeias.
4.Os AFNs podem ser convertidos em AFDs equivalentes com base em algumas regras
de acordo com o estado atual, símbolo de entrada e próximo estado. Observe o AFN a
seguir:
 Que autômato finito determinístico aceita a mesma linguagem?
A imagem acima mostra a alternativa correta, uma vez que os dois estados de aceitação
validam as duas entradas unicamente aceitas.
Considerando d como transição, o autômato reconhece apenas duas cadeias: ba e baa.
Consequentemente, a transição d(q2, a) = q2 gera um laço infinito, ocasionando uma sequência
de qualquer tamanho com símbolo a. Apesar de aceitar a cadeia ba, não aceita baa, e sim bba,
o que faz com que não seja um AFD equivalente ao AFN da questão.
O estado de aceitação informado foi q1, o que invalida a aceitação fornecida pelo AFN de
origem; além disso, foi provado, com a construção do AFD, que não é impossível sua geração.
5. A notação formal relacionada a um AFN tem por objetivo, além de sua devida
formalização, instruir sobre características e estado da computação atual do autômato.
Considere que determinada computação de um AFN esteja na seguinte situação para a
entrada 011:
Com base nessa tabela, pode-se afirmar que:
Resposta correta.
B.
A computação está no estado q0 e q1 em "paralelo", avaliando o símbolo 0 .
Na tabela é possível perceber que a computação ainda não foi completa, uma vez que
ainda existe um símbolo 0 a ser analisado. Além disso, observe que, na penúltima e
última linhas, ao ser lido 1 no estado q0, o autômato pode ir tanto para q1 como
permanecer em q0. Ao mesmo tempo, por ter os dois estados e um símbolo 0 na
entrada, ocorrerá a computação "em paralelo" para os dois casos. Para finalizar, em
nenhum momento é exibida alguma transição a partir de q1, e a transição irá depender
da entrada (0 ou 1).
1.
Pode-se afirmar que a propriedade de fecho consiste em um conjunto de operações sobre
as linguagens regulares que produzem uma nova linguagem também regular. Essas
operações têm como intuito possibilitar a união, a interseção, a concatenação, entre
outras operações sobre as linguagens regulares.
Visto isso, considere as operações de união e concatenação. Assim, dadas as linguagens
L1 = ｛a, aaa, b｝, L2 = {bb, c} e L3 = {aa, cc, d} sobre o ∑ = {a, b, c, d}, informe qual é a
linguagem obtida por L4 = ( L1∪ L2).L3 .
Resposta correta.
B.
L4 = ｛aaa, acc, ad, aaaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd｝.
Considere L4 = ( L 1∪ L 2). L 3.
Em um primeiro momento, obtém-se o resultado de ( L 1 ∪ L 2) e, posteriormente,
concatena-se a L 3. Assim, tem-se:
L4 = ｛a, aaa, b, bb, c｝.{aa, cc, d}
Por fim, deve-se concatenar o resultado da união de L 1 e L 2.
Nesse sentindo, a resposta é dada por:
L4 = {aaa, acc, ad, aaaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd}
Perceba que, em nenhuma das linguagens, há o operador ε. Assim, este não aparecerá
como parte da nova linguagem.
2. Semelhante ao uso nas linguagens regulares, também é possível utilizar operadores
diretamente nos símbolos, pois, dada uma Linguagem L = ｛a｝, se pode representá-la
simplesmente por a. Desse modo, ao inserir o operador estrela, sobre a, por exemplo,
teremos como resultado {ε, a, aa, aaa,...}.
Tendo em vista o exposto, dadas as linguagens a seguir, marque a opção que representa
uma linguagem que produz uma cadeia que começa e termina com o mesmo símbolo,
considerando que ∑={a,b}:
Resposta correta.
D.
(a ∑* a)∪ (b ∑* b)∪ a∪ b.
A questão solicita uma linguagem que inicia e termina com o mesmo símbolo. Desse
modo, considerando ∑=｛a,b｝, tem-se ( a ∑* a), no qual uma cadeia deve ser iniciada e
terminada com o símbolo a e ∑* representa qualquer símbolo do alfabeto, inclusive ε.
Seguindo o mesmo estilo, teremos (b ∑* b), no qual a cadeia deverá iniciar e terminar
com o símbolo b.
Por fim, deve-se considerar também a leitura dos símbolos a e b, em que terminam e
começam com o mesmo símbolo. Assim, temos:
(a ∑* a)∪ (b ∑* b)∪ a∪ b
3. As operações de fechamento, ou operações de fecho, sob linguagens regulares,
podem ser definidas como aquelas que, quando aplicadas a elas, produzem uma nova
linguagem também regular.
Considere as informações a seguir:
Dada uma linguagem regular L = ｛00, 01, 11, 011｝ sob ∑ = {0, 1}.
Analise as cadeias a seguir e informe quais fazem parte da linguagem L*:
1- 00011100011
2- 00111010000
3- 11010001111
4- 01101000100
5- 11011110111
Resposta correta.
E.
Fazem parte de L* as opções 1, 3, 4 e 5.
Considerando a linguagem regular como L = ｛00, 01, 11, 011｝, tem-se que:
1- 00011100011 = 00 01 11 00 011
2- 00111010000 = 00 11 e regra quebrada em 1010000.
3- 11010001111 = 11 01 00 011 11
4- 01101000100 = 011 01 00 01 00
5- 11011110111 = 11 011 11 01 e 11
Portanto, estão corretas apenas as opções 1, 3, 4 e 5.
4.
Determinada linguagem regular L é formada por um conjunto de símbolos pertencentes a
um alfabeto ∑. A partir dessa linguagem L, é possível obter um conjunto de cadeias que
possibilitam elaborar um modelo computacional a ser aplicado em diversas situações,
como, por exemplo, buscar determinados caracteres em um texto, fazer uma busca por
meio de motores de buscas da web, entre outras.
Considerando as linguagens apresentadas a seguir, relacione a primeira com a segunda
coluna, verificando se cada cadeia obtida na segunda coluna pertence à da primeira.
Posteriormente, marque o item que representa a ordem correta das linguagens
reconhecidas.
Considere ∑=｛1,0｝.
Primeira coluna:
L1 = 1*∪ 0*
L2 = 1 (01)* 0
L3 = ∑*1∑*0∑*1∑*
L4 = (ε∪ 1) 0*
Segunda coluna:
( ) 0, 10, 100
( ) 10, 1010, 101010
( ) ε, 11, 00
( ) 101, 11011, 101111
A ordem correta obtida na segunda coluna é:
Resposta correta.
D.
L4, L2, L1, L3.
Nesta resolução, deve-se verificar cada cadeia do item e a qual linguagem ela pertence.
Veja:
( ) 0, 10, 100
Ao analisar as linguagens, a primeira cadeia, 0, poderá fazer parte de L1 ou L4. Assim,
deve-se analisar o valor seguinte.
10 - pode pertencer à linguagem L1, L2 ou L4.Desse modo, passa-se para o passo
seguinte.
100 - este valor também pode pertencer a L1 ou L4. Dessa forma, considera-se que é
possível ter L1 ou L4 para essa opção.
( ) 10, 1010, 101010
10 - como visto, pode pertencer a L1, L2 ou L4.
1010 - esta cadeia é aceita por L2 e L3.
101010 - esta cadeia também é aceita por L2 e L3.
Desse modo, neste item, é possível afirmar que tem valor L2.
( ) ε, 11, 00
ε, apenas L1 e L4 aceitam ε como parte da linguagem.
11 - apenas L1 aceita esta cadeia.
00 - apenas L1 e L4 aceitam esta cadeia.
Isto é, neste item, tem-se a linguagem L1.
( ) 101, 11011, 101111
101 - esta cadeia é aceita apenas por L3.
11011 - esta cadeia é aceita por L3.
101111 - esta cadeia é aceita apenas por L3.
Desse modo, tem-se L4, L2, L1 e L3 como alternativa correta.
5.
Verificar se uma linguagem é regular é fundamental, pois, em caso positivo, será possível
solucionar determinado problema de forma simples e com tempo de execução ótimo.
Existem algumas maneiras de verificar se uma linguagem é regular. Um exemplo é por
meio do uso de AFDs. Por outro lado, há a possibilidade de verificar se dada linguagem é
não regular. Para isso, uma das formas mais utilizadas é o lema do bombeamento.
Com base Σ = ｛a, b｝, analise as linguagens a seguir e marque a opção referente a uma
linguagem não regular.
Você acertou!
E.
L5 = ｛w | w possui um número de a's igual ao número de b's｝ .
Para a resolução desta questão, inicia-se pela forma mais simples, ou seja, por meio da
tentativa da elaboração de um autômato finito que represente as linguagens
Quanto à linguagem L5, houve certa dificuldade em elaborar um autômato que a represente.
Isso nos leva a ter indícios de que L5 não é uma linguagem regular. Desse modo, prova-se por
meio do lema do bombeamento.
Assumimos que L5 é uma linguagem regular.
Desse modo, determinada cadeia w pode ser dividida em xyz.
No qual y ≠ ε;
|xy| <= p e
xyiz∈ L5 para todo i >= 0
Considera-se a cadeia aaabbb e dividirmos em x = a, y = aa e z = bbb; ao bombear y, teremos
uma cadeia como, por exemplo, aaaaabbb, o que torna a quantidade de a's diferente da
quantidade de b's, tornando a linguagem não regular. 
1.
Determinada empresa Z pretende criar os e-mails institucionais de seus funcionários.
Para isso, ela visa a fazer uso de expressões regulares. Assim, considerando uma cadeia
qualquer w, faz-se necessário elaborar e-mails do tipo w@empresaZ.com, de forma que
|w| tem tamanho mínimo igual a 1 e máximo igual a 4.
Tendo em conta um alfabeto Σ = ｛a, b｝, um funcionário da empresa elaborou, então, uma
expressão regular da seguinte forma
(a + b)(ε + a + b)(ε + a + b)(ε + a + b). Tendo em vista o alfabeto,
 a expressão e as orientações dadas, informe quantas possibilidades existem para criação
de e-mails.
Resposta correta.
C.
30.
A partir da expressão (a + b)(ε + a + b)(ε + a + b)(ε + a + b), considerando 2 símbolos
do alfabeto e, respectivamente, cadeias de tamanho 4, 3, 2 e 1, tem-se que:
24 + 23 + 22 + 21 = 30
Desse modo, é possível obter as seguintes cadeias: ｛a, b, aa, bb, ab, ba, aaa, aab, abb,
aba, bbb, baa, bab, bba, aaaa, aaab, aabb, aaba, abbb, abab, abaa, abba, bbbb, bbba,
bbaa, bbab, baaa, baba, babb, baab｝.
2.
Existem diversas maneiras de representar determinada linguagem regular, seja por
autômatos finitos, seja por expressões regulares. Ao optar pela segunda, ainda assim, há
diversas possibilidades capazes de originar uma mesma linguagem.
Tendo em vista o informado e o alfabeto Σ = ｛0,1｝, considere a expressão 0 * (100) * (0 *
(100) *) * e informe qual das opções a seguir produz o mesmo conjunto de cadeias:
Resposta correta.
E.
(0 + 100)*
Considerando 0 * (100) * (0 * (100) *) *, é possível perceber que a expressão
basicamente consiste em operações de concatenação e fechamento.
É possível alterar a expressão dada por.
(0 * (100) *) + (0 * (100) *) *.
Ao analisar a expressão alterada, pode-se perceber que (0 * (100) *) e (0 * (100) *) *
produzem as mesmas cadeias; assim, é possível excluir uma das extremidades.
Ao escolher (0 * (100) *) *, resta (0 * (100) *), que pode ser transformada em (0 +100) *,
produzindo, ainda assim, o mesmo conjunto de cadeias.
3. As linguagens regulares podem ser denotadas por autômatos finitos ou expressões
regulares. No primeiro caso, ou seja, com relação aos autômatos finitos, podem ser
representadas por um conjunto de estados, um conjunto finito de símbolos, o qual
chamamos de alfabeto, uma função de transição, um estado inicial e, por fim, apenas um
ou um conjunto de estados finais. No segundo caso, as expressões regulares costumam
ser representadas por um conjunto de símbolos de um alfabeto, símbolos que
representam operações (concatenação, fecho estrela e união) e por parênteses, com o
intuito de definir uma precedência.
Há casos em que a representação de uma linguagem regular a partir de um autômato
finito se torna a melhor opção, pois, de acordo com o problema, ela apresenta um formato
de interpretação mais simples. No entanto, há momentos em que a expressão regular se
torna indispensável. Desse modo, é possível converter um autômato finito em uma
expressão regular.
Tendo em vista o apresentado, analise o autômato a seguir e informe quais expressões
regulares poderão denotar a mesma linguagem:
 Considere:
I. (ab*a+ba*b)a*baa +(ab*a+ba*b)a*bbb
II. (a+b)(b+a)*(a+b)a*b(a+b)(a+b)
III. (ab*a + ba*b)a*b(aa + bb)
IV. (ab*a)+(ba*+b)*ab(aa)+(bb)
Entre as opções, estão corretas apenas:
Resposta correta.
B.
I e III.
Considerando o estado inicial do autômato, ao efetuar a leitura e ir para o estado q1 e,
posteriormente, q5, tem-se que: ab*a.
Em outro sentido, ao optar o caminho do estado q0 para q4 e, posteriormente, q5,
temos que b*ab. Desse modo, obtém-se a primeira parte da expressão regular:
(ab*a + ba*b).
Dando sequência, no estado q5, temos a leitura de qualquer quantidade de a; assim, a*
e, indo para q2, uma leitura obrigatória de b. Desse modo:
(ab*a + ba*b)a*b.
Nesse ponto, ao chegar a q2, há duas possibilidades. Seguir para o caminho q3 e
posteriormente finalizar em q8, ou seguir a leitura para q6 e finalizar em q8. Desse
modo, pode-se representar da seguinte maneira:
(ab*a + ba*b)a*baa + (ab*a + ba*b)a*bbb
ou
 (ab*a + ba*b)a*b(aa + bb).
4.
As expressões regulares são uma maneira formal de descrever linguagens regulares a
partir de conjuntos de símbolos e/ou caracteres especiais que formam determinada regra
a partir de operadores de concatenação, união e fecho estrela.
Dado o exposto, considerando um alfabeto Σ = ｛a, b｝ e uma linguagem L = {w∈ Σ |(anbm)
na qual n > 1 e m ≤ 1}, marque a alternativa que representa o complemento da linguagem
dada por meio de uma expressão regular.
Resposta correta.
E.
(a + ε)bbb*.
O complemento é uma operação de fechamento sob linguagens regulares. Desse
modo, quando aplicada a uma linguagem regular, essa expressão produz uma nova
linguagem regular.
Considerando n > 1 e m ≤ 1, o complemento são todos os valores que não
correspondem a estes, ou seja n ≤ 1 e m > 1; assim, ao considerar a expressão anbm,
temos inicialmente uma quantidade de a’s de no máximo 1 e uma quantidade de b’s de
no mínimo 2.
A partir do exposto, tem-se que:
Para aa* + (b + ε), pode-se fazer uso da cadeia aaaaa, o que quebra a regra de n ≤ 1 e
m > 1.
Para (a + ε)*(b + ε), pode-se fazer uso da cadeia aaab, o que também quebra a regra n
≤ 1 e m > 1.
Em (a*)bbb*, pode-se dispor de qualquer quantidade de a e, no mínimo, duas
quantidades de b, o que também quebra a regra dada.
Na expressão regular (a + aa + aaa + ε)* b*, pode-se fazer uso da cadeia bbbb, que
também não corresponde à regra informada.
Por fim,
Para (a + ε)bbb*
(a+ε), representa a leitura de apenas um ou nenhum a, ou seja, n ≤ 1 e bbb* torna
obrigatória a leitura de ao menos dois b’s, isto é, m > 1.
Desse modo, a opção correta é (a + ε)bbb*.
5.
As expressões regulares são utilizadas para denotar linguagens regulares. A partir delas,
é possível fazer uso de operações de maneira bastante simples esucinta. Quando
utilizadas em linguagens de programação, normalmente são aplicadas com o intuito de
verificar, por meio de determinada regra, se um conjunto de símbolos pertence a
determinado padrão. Desse modo, pode-se inferir que estas podem ser utilizadas para
verificar se determinada entrada corresponde a um padrão válido, como um e-mail.
Dado o exposto, considerando um alfabeto Σ = ｛a, b｝ e uma expressão regular (a + b) * a
(a + b) * a (a + b) *, marque a alternativa que melhor representa a expressão apresentada.
Resposta correta.
D.
O conjunto de todas as cadeias contendo pelo menos dois a’s.
Quanto às opções, tem-se:
Conjunto de todas as cadeias que têm ao menos um b — perceba que é possível a
elaboração da cadeia babab deste, o que torna essa afirmativa incorreta.
O conjunto de todas as cadeias contendo a subcadeia aa — realmente há a
possibilidade de formar cadeias de modo a existir a subcadeia aa; no entanto, tal qual
citado anteriormente, a cadeia babab faz parte da linguagem, o que torna essa opção
incorreta.
O conjunto de todas as cadeias contendo no máximo dois a’s — a partir da expressão
dada, é possível obter a cadeia aaaa, o que a torna incorreta.
O conjunto de todas as cadeias contendo pelo menos dois a’s — de fato, a expressão
torna obrigatória a leitura de pelo menos dois a’s: perceba em (a + b) * a (a + b) * a (a +
b) *.
O conjunto de todas as cadeias que começam e terminam com a ou b — perceba que,
a partir do momento que existe a obrigatoriedade do uso de no mínimo dois a’s, essa
afirmativa já se torna falsa, pois não é possível gerar a cadeia ab, por exemplo.
UNIT2
1.
Uma gramática é dita regular se ela é uma gramática linear à direita (GLD), gramática
linear à esquerda (GLE), gramática linear unitária à direita (GLUD) ou gramática linear
unitária à esquerda (GLUE). Desse modo, ao reconhecer uma gramática como alguma das
citadas, logo ela será uma gramática regular e, portanto, representará uma linguagem
regular.
Quanto às gramáticas citadas, elas são equivalentes. Desse modo, apesar de o formato
de produção entre elas ser diferente, ainda assim produzem a mesma linguagem. Um
exemplo de gramática linear é apresentado a seguir.
S → Aa | Bb
A → Bb | Cc
B → a | Bc
C → b
Dito isso, considere a gramática linear unitária à esquerda (GLUE) apresentada e marque
a alternativa que representa a expressão regular equivalente.
Você acertou!
A.
ac*b + ac*ba + bca.
Como forma de provar qual a alternativa correta, faça as comparações com as palavras
produzidas pela gramática com as palavras produzidas pela expressão regular.
A alternativa ac*b + ac*ba + bca será analisada a seguir.
Tem-se como expressão regular ac*b + ac*ba + bca.
Assim, é possível dividi-la em: ac*b, ac*ba e bca.
Em ac*b, escolha a palavra acb e veja o processo de derivação a seguir:
S⇒ Bb
B⇒ Bcb
B⇒ acb
Para ac*ba, escolha a palavra acba:
S⇒ Aa
A⇒ Bba
B⇒ Bcba
B⇒ acba
Em bca, tem-se:
S⇒ Aa
A⇒ Cca
C⇒ bca
Portanto, essa alternativa está correta.
Na alternativa acb + ac*ab + bca, conforme visto, acb é aceita. Desse modo, veja para a
produção acab:
S⇒ Bb
B⇒ ab
Note que o processo é encerrado aqui. Portanto, essa alternativa está incorreta.
Na alternativa ac*b + acbac + bca, conforme visto, acb é aceita. Portanto, será avaliada
a produção de acbac.
Note que S não produz o símbolo c. Dessa forma, essa alternativa está incorreta.
Na alternativa acab + acc*b + bca, veja a produção da palavra acab:
S⇒ Bb
B⇒ ab
Portanto, essa alternativa está incorreta.
Na alternativa acb + ab*ab + bca, conforme visto, acb é aceita. Assim, será verificada a
produção de abab:
S⇒ Bb
B⇒ ab
Dessa forma, essa alternativa está incorreta.
2.
Conforme Ricarte (2008), as gramáticas regulares, embora tenham poder de expressão
mais limitado, são também utilizadas para a representação de alguns aspectos
importantes nas linguagens de programação, considerando, por exemplo, os
identificadores, utilizados para representar nome de variáveis ou funções. Para que eles
sejam válidos, é importante inserir regras, como os identificadores que devem iniciar com
uma letra para que posteriormente possam ter letras ou dígitos, entre outras restrições
dadas.
Dito isso, analise a gramática a seguir, as suas regras/restrições e, posteriormente,
marque a alternativa que representa a linguagem gerada por ela.
S -> 0S | 1S | 0A
A -> ε
Você acertou!
E.
L = ｛w∈ {0, 1｝ * | w termina com 0}.
Para verificar a alternativa correta, é necessário analisar o que cada linguagem
apresentada produz. Desse modo, será analisado cada item da questão.
L = ｛w∈ {0, 1｝ * | w tem a mesma quantidade de 0's e 1's}
A linguagem apresentada nessa alternativa possibilita obter diversas quantidades de 0’s
ou 1’s, inclusive nenhuma, mas que essa quantidade de símbolos seja idêntica entre
eles, o que não condiz com a gramática apresentada, pois por meio da gramática dada
é possível produzir palavras como 010, que tem uma quantidade diferente de 0’s em
comparação à quantidade de 1’s. Portanto, essa alternativa está incorreta.
L = {w∈ {0, 1} *}
Essa alternativa apresenta uma linguagem que produz qualquer quantidade de 0’s e 1’s
e em qualquer ordem. Desse modo, a palavra 0101 não é gerada pela gramática, o que
torna essa alternativa incorreta.
L = {0n 1m | n, m ≥ 0}
Nessa alternativa, é possível produzir palavras como {ε, 0, 1, 00, 01, 001, ...}. Note que
se a palavra obtiver ao menos um 0 e um 1, o primeiro deverá anteceder ao segundo,
isto é, os 0’s deverão vir antes dos 1’s, o que não é uma regra existente na gramática
apresentada e, portanto, torna essa alternativa incorreta.
L = {0n | n ≥ 0}∪ {1n | n ≥ 0}∪ {0n 1n | n ≥ 0}
A linguagem apresentada nessa alternativa produz diversas quantidades de 0’s unida à
linguagem que produz diversas quantidades de 1’s unidas à linguagem na qual produz
diversas quantidades de 0’s e 1’s, nessa ordem e com a mesma quantidade. Para
provar que a alternativa é incorreta, escolheremos a cadeia 01, que faz parte da
linguagem fornecida, mas que não faz parte da gramática apresentada.
L = {w∈ {0, 1} * | w termina com 0}
Nessa alternativa, é possível obter diversas quantidades de 0’s e 1’s, mas, como regra,
apenas as palavras que terminam em 0. Portanto, essa é a alternativa correta.
3. Conforme Anderson (2006), um autômato, como o exemplo a seguir, é um dispositivo
que reconhece ou aceita certos elementos de um alfabeto finito (Σ) e, desse modo, os
elementos aceitos por ele são um subconjunto de Σ*, isto é, ele possibilita a leitura de
palavras de uma determinada linguagem.
De forma semelhante, as gramáticas, a partir de um conjunto de regras, quando aplicadas
de forma sucessiva, têm o poder de gerar palavras e estas últimas formam uma
linguagem.
Considerando que os autômatos finitos e que as gramáticas regulares denotam
linguagens regulares, portanto são equivalentes, marque a alternativa que produz uma
gramática equivalente ao autômato finito apresentado anteriormente.
Você acertou!
A.
S → 0A | 1B
A → 0D | 1A
B → 0B | 1C
C → 1
D → 0
Para obter a resposta correta, veja a análise de cada uma das gramáticas
apresentadas.
S → 0A | 1B
A → 0D | 1A
B → 0B | 1C
C → 1
D → 0
Inicialmente, tem-se a produção um dos dois símbolos, 0 ou 1. Considerando a escolha
de 0, deve-se partir para a variável A, a qual tem nenhuma ou diversas produções do
símbolo 1 ou 0, sendo que, neste último caso, deve-se partir para a variável D,
produzindo 0 e encerrando o processo. Considerando a escolha de 1, poderão ser
produzidas diversas quantidades de 0's, inclusive nenhuma, ou produzir o valor 1 e,
então, partir para a variável C, produzindo novamente 1 e encerrando o processo.
Portanto, essa alternativa está correta.
S → 0A | 1B
A → 0A | 1A
B → 0B | 1B
C → 1
D → 0
De forma semelhante à alternativa anterior, há a produção de um dos dois símbolos 0
ou 1. Ao optar pela produção do símbolo 0, deve-se partir para a variável A, que poderá
produzir 0 ou 1 e permanecerá nessa variável.
Portanto, essa alternativa está incorreta.
S → 0A | 1B
A → 1A
B → 0B | 1C
C → 1D
D → 0E
E→ε
Ao optar pela produção de 0, deve-se partir para a variável A, que produzirá diversas
quantidades de 1's, inclusive nenhuma e, nesse caso, não haverá a possibilidade de
continuar a produção de outro símbolo.
Portanto, essa alternativa está incorreta.
S → εA
A → 0B | 1C
B → 1B |0D
C → 0C | 0E
D → 0
E → 1
O estado inicial proporcionará uma produção vazia ε e partirá para a variável A. Nesta,
pode-se produzir o símbolo 0 ou 1. Ao produzir 0, deve-se partir para B, que poderá
produzir diversas quantidades de 1's ou 0; partindo para D, em D produzirá 0 —
portanto, aceita até esse momento. Ao iniciar o processo produzindo 1, deve-se partir
para C, que poderá produzir diversas vezes o valor 0, sendo no mínimo uma vez, o que
torna a alternativa incorreta.
S → 0A | 1B
A → 0D | 1A
B → 0B | 1C
C → 1
D → 1
Tem-se a produção de 0 ou 1. Ao escolher 0, deve-se partir para A. Em A, pode-se
produzir diversas quantidades de 1 ou produzir 0 e partir para D. Em D, é produzido o
símbolo 1, o que torna a alternativa incorreta.
4.
As gramáticas regulares têm o poder de denotar linguagens regulares. Desse modo, tais
gramáticas têm as mesmas restrições e simplicidades dessas linguagens.
Pode-se afirmar que uma gramática regular é uma quádrupla no formato G = (V, T, P ,S).
Nesse sentido, V representa o conjunto de variáveis, T os símbolos terminais, P as regras
de produção e S o símbolo inicial.
Analisando as regras de produção, considere a gramática regular a seguir.
S → bA
A → aB | bS | ε
B → aA
Tendo em vista a gramática apresentada, derive as palavras a seguir e marque a
alternativa que representa apenas as palavras que são geradas pela gramática regular
ilustrada anteriormente.
I. baabbaa
II. bbbabab
III. bbbbabb
IV. baabbba
V. bbbaabb
Com base nas palavras derivadas, é correto afirmar que estão corretas as afirmativas:
Resposta correta.
C.
I e V, apenas.
Para verificar quais são as palavras que pertencem à linguagem denotada pela
gramática dada, é preciso efetuar o processo de derivação em cada uma delas.
I. baabbaa
S⇒bA
A⇒baB
B⇒baaA
A⇒baabS
S⇒baabbA
A⇒baabbaB
B⇒baabbaaA
A⇒baabbaa
Portanto, é gerada pela gramática.
II. bbbabab
S⇒bA
A⇒bbS
S⇒bbbA
A⇒bbbaB
No entanto, B não gera a leitura do símbolo a, logo essa palavra não é gerada.
III. bbbbabb
S⇒bA
A⇒bbS
S⇒bbbA
A⇒bbbbS
No entanto, S não gera o símbolo a, logo essa palavra não é gerada.
IV. baabbba
S⇒bA
A⇒baB
B⇒baaA
A⇒baabS
S⇒baabbA
A⇒baabbbS
No entanto, S não gera o símbolo a, logo essa palavra não é gerada.
V. bbbaabb
S⇒bA
A⇒bbS
S⇒bbbA
A⇒bbbaB
B⇒bbbaaA
A⇒bbbaabS
S⇒bbbaabbA
A⇒bbbaabb
Portanto, é gerada pela gramática.
Conforme apresentado, as afirmativas corretas são I e V.
5.
Conforme Kandar (2013), o tipo 3 de gramática é chamado de "gramática regular" e tem
todas as produções dada pela seguinte forma:
A →a ou A →aB, em que A, B são variáveis e a é um símbolo terminal.
Considerando o exporto e de acordo com a hierarquia de Chomsky (1956), o tipo 3
compreende as linguagens regulares. Sendo assim, as gramáticas regulares
compreendem as produções dessas linguagens.
Veja a seguir um exemplo de uma gramática regular.
S → aA | bB
A → aC | a
B → bD | b
C → aA
D → bB
 Considerando que, conforme Ricarte (2008), as expressões regulares representam uma
forma alternativa de expressar uma linguagem regular, analise a gramática regular
apresentada anteriormente e informe qual expressão regular é equivalente a ela.
Você acertou!
C.
aa(aa)*+ bb(bb)*.
Nessa questão, será provado qual alternativa está correta a partir de produções dadas
pela gramática.
Ao analisar a gramática em questão, perceba que a partir dela são produzidas palavras
como ｛aa, bb, aaaa, bbbb, ...｝ ou seja, um número par de a’s ou b’s a partir de 2.
Analisando as alternativas:
(a + b) (a + b)
Note, nessa expressão, que a palavra aaaa não é produzida. Portanto, essa alternativa
está incorreta.
(a + b) + (a + b)*
Na expressão dada, há a possibilidade de palavras como a, b, ab, aab, entre outras, o
que não faz parte das produções dadas pela gramática apresentada. Portanto, essa
alternativa está incorreta.
aa(aa)*+ bb(bb)*
Note que nessa alternativa existe um número mínimo de dois a’s ou dois b’s, sendo que
as próximas quantidades correspondem a repetições pares desses símbolos. Portanto,
essa alternativa está correta.
(a + b)*
A expressão dada nessa alternativa produz qualquer tipo de palavra sobre o alfabeto Σ=
{a,b}, o que não corresponde à gramática dada. Portanto, a alternativa está incorreta.
(a + b)(a+b)*
Nessa alternativa, há a possibilidade de palavras como a, b, abb, entre outras, o que
não corresponde à gramática dada. Portanto, a alternativa está incorreta.
1. Autômatos de pilha determinísticos (APDs) são estruturas formais de
grande importância, visto que constituem uma base para se construir
reconhecedores para muitas linguagens que ocorrem na prática.
Para uma palavra ser reconhecida, é necessário que, após os símbolos de entrada serem
lidos, pelo menos uma das condições a seguir seja satisfeita:
(1) Um estado final seja atingido.
(2) A pilha esteja vazia.
Considere o autômato de pilha determinístico a seguir:
Qual das palavras a seguir é aceita por esse APD?
Você acertou!
D.
12021.
O APD mostrado reconhece a linguagem w0wR, em que w = ｛1|2｝*. Ou seja, ele
reconhece palavras formadas por uma sequência de zero ou mais combinações de
dígitos 1 e 2, seguida de apenas um dígito 0, seguido dos dígitos da sequência inicial
em ordem inversa (R = reverso).
As palavras 10, 1012, 12012 e 120021 não atendem a esse requisito; logo, serão
rejeitadas pelo APD.
A palavra 12021 é a única alternativa que contém uma palavra aceita por esse
autômato.
2 .Os APDs são importantes porque permitem construir reconhecedores eficientes para
uma classe de linguagens muito usada na computação. A definição de autômato de pilha
determinístico basicamente acrescenta uma pilha a um autômato finito. Para que haja
determinismo, não deverá ser possível mais de uma transição ser definida para uma
mesma configuração instantânea; em outras palavras, em um estado qualquer do APD,
qualquer que seja o próximo símbolo de entrada e qualquer que seja a situação atual da
pilha, no máximo uma transição deverá ser possível.
Considere os autômatos de pilha a seguir:
Quais deles são determinísticos?
Resposta correta.
D.
I e II.
Para os autômatos I e II, em um estado qualquer, qualquer que seja o símbolo de
entrada a ser lido e qualquer que seja a situação atual das suas pilhas, há no máximo
uma transição possível. Logo, tanto A como B são autômatos de pilha determinísticos.
No autômato III, a partir do estado 1, há duas transições possíveis para a entrada 1 e
topo de pilha epsilon: uma que mantém o estado em 1 (loop) e outra que leva para o
estado 2. O mesmo ocorre com o símbolo de entrada igual a 2. Isso torna esse
autômato de pilha não determinístico.
3. Um aluno, estudando sobre linguagens formais, decidiu construir um autômato de
pilha determinístico para reconhecer a linguagem: ｛0n12n | n ≥ 0｝. Ele acabou construindo
o seguinte autômato:
 Entretanto, após realizar alguns testes, ele verificou que o autômato não funcionava
conforme o esperado. Qual transição deve ser substituída nesse APD para que ele passe
a reconhecer a linguagem proposta?
Resposta correta.
C.
Transição 3.
Nesse APD, sempre que for lido um valor 0 na entrada, dois símbolos X serão inseridos
na pilha. Quando os valores iguais a 1 forem lidos, apenas um símbolo X deve ser
removido da pilha. Para que a palavra seja aceita, é necessário que a pilha esteja vazia
(Z) e que o autômato se encontre no estado q2.
A transição 1 está correta. Ela é responsável por ler um valor 0 e empilhar XX. A
transição 2 também está correta, pois, ao ler um valor 1 da entrada, um X deve ser
removido da pilha, e somente valores 1 devem ser fornecidos. A transição 3, entretanto,
está incorreta, pois, em vez de remover um símbolo X, ela remove dois (XX) da pilha a
cada símbolo 1 lido. A transição 4 é válida, pois não pode ser iguala zero; logo, pode
haver zero ocorrências de zeros e uns. A transição 5 será executada quando, após
terminada a entrada de símbolos, a pilha se encontrar vazia (Z); o autômato será levado
para o estado final q2, e a palavra será reconhecida.
A única transição que precisaria ser alterada seria a transição 3.
4. Uma estudante criou um sistema para validar expressões aritméticas entre parênteses,
formadas com operadores de soma e multiplicação. Para isso, ela implementou
parcialmente o seguinte autômato de pilha:
 Quais transições devem ser inseridas nas lacunas A e B para que esse autômato funcione
corretamente?
Você acertou!
D.
A: ( , ε, X
B: + , ε, ε e *, ε, ε 
Para realizar o controle de abertura e fechamento dos parênteses, a transição A precisa
ler ( , ignorar o estado atual da pilha (ε) e empilhar o símbolo de controle X, ou seja, A: (
, ε, X.
Como se deseja trabalhar com expressões contendo somas e multiplicações, é
necessário que a transição B permita ler esses símbolos. Entretanto, a leitura de + ou *
não deve influenciar a pilha; logo, suas transições devem ser: B: + , ε, ε e *, ε, ε.
A alternativa A: ( , X, ε é incorreta, pois A remove o símbolo X em vez de inseri-lo na
pilha.
A opção A: ( , ε, ε é incorreta, pois não insere o símbolo de controle X na pilha.
A opção B: + , ε, X e *, ε, X está incorreta, pois a leitura de operadores de soma e
multiplicação não deve interferir no símbolo de controle na pilha.
5.
Os APDs têm capacidade de reconhecimento maior do que os autômatos finitos.
Enquanto estes últimos reconhecem apenas linguagens regulares, os APDs reconhecem
a classe de linguagens livres de contexto determinísticas.
Considere as linguagens a seguir:
I) ｛03n12n | n ≥ 0｝
II) {wwR | w∈ {1, 2} ∗}
III) {w0wR | w∈ {1, 2} ∗}
Para quais dessas linguagens é possível construir um APD?
Resposta correta.
E.
I e III.
1. As transições em autômatos de pilha apresentam quatro informações: o
símbolo lido, o símbolo no topo da pilha, o símbolo ou a cadeia de
símbolos a serem substituídos no topo da pilha e o estado destino (que
pode ser o mesmo).
Analise a transição a seguir e assinale a alternativa correta.
Resposta correta.
B.
A transição é feita quando o símbolo lido da entrada é a e o topo da pilha é b. O símbolo b do
topo da pilha é desempilhado.
A transição tem duas condições: o símbolo lido da entrada deve ser a (primeiro campo)
e o topo da pilha deve ser b (segundo campo). O terceiro campo informa que o símbolo
b de topo da pilha deve ser substituído por palavra, o que efetivamente é a mesma ação
de desempilhar b. A transição consome o símbolo a da entrada e é válida.
2. Autômatos de pilha podem ter várias combinações de transições
diferentes. Entender cada uma delas é fundamental para a construção
correta desse tipo de autômato e, também, para a interpretação de
diagramas.
Analise o autômato a seguir e assinale a alternativa correta que descreve a linguagem
que ele reconhece.
Resposta correta.
E.
｛0n1n0n | n > 1｝.
No estado p, o autômato de pilha em questão empilha, para cada símbolo 0 lido na
entrada, mais dois símbolos na pilha além do topo. No estado q, para cada símbolo 1
lido, é desempilhado exatamente um símbolo 0 do topo da pilha. O mesmo acontece no
estado r, porém o símbolo lido é 0. Quando não há mais símbolos para serem lidos e o
topo da pilha for o símbolo inicial, é o caso de a palavra ser aceita. Note que o autômato
não aceita a cadeia vazia como entrada, portanto a menor cadeia aceita é de tamanho
3, o que explica o n > 1.
3. A pilha de um autômato de pilha é a estrutura fundamental para que esse
modelo seja mais poderoso que os autômatos finitos mais simples. A pilha
funciona como uma memória primitiva, não podendo acessar qualquer
posição da pilha, apenas o topo.
Considere o autômato a seguir e assinale a resposta correta.
Resposta correta.
D.
O autômato de pilha em questão é válido mesmo que o topo da pilha seja substituído por ele
mesmo em toda transição.
Transições de autômatos de pilha podem substituir o topo da pilha pelo mesmo símbolo,
por nenhum símbolo (cadeia vazia), por um símbolo diferente do topo ou até mesmo por
uma cadeia de símbolos. O autômato em questão é válido e reconhece a linguagem
regular com as palavras de tamanho par. Esse autômato de fato simula um autômato
finito mais simples que reconhece o conjunto de cadeias de tamanho par.
4. A transição em autômatos finitos dependia apenas do estado atual e do
índice do símbolo da cadeia. Em autômatos de pilha, a transição também
depende do símbolo no topo da pilha para ser feita.
Analise as transições do autômato de pilha a seguir considerando que pilha tem dois
elementos conforme ilustrado na figura e que o autômato se encontra no estado q.
Assinale a alternativa correta:
Resposta correta.
A.
Independentemente do símbolo lido da cadeia de entrada, nenhuma transição será feita, pois a
é o topo da pilha e as transições requerem b como topo.
Como o símbolo do topo da pilha é a e as duas transições só podem ser feitas quando o
topo da pilha é b, nenhuma transição será feita e esse ramo de execução morrerá. As
duas transições são válidas, a transição que vai do estado q para r desempilha o
símbolo b do topo da pilha e a transição que fica no estado q adiciona mais dois
símbolos b ao topo da pilha anterior.
5. Autômatos de pilha não determinísticos são mais poderosos que
autômatos de pilha determinísticos. A linguagem wwr tem uma variação, a
linguagem w#wr, a qual requer que o símbolo do meio da palavra, ou seja,
entre w e wr, seja uma cerquilha.
Considere o diagrama de um autômato de pilha a seguir, que tem Z como símbolo inicial
de topo de pilha e o conjunto ｛0,1,#｝ como alfabeto de entrada.
Assinale a alternativa correta.
Resposta correta.
B.
O autômato reconhece a linguagem w#wr, que segue apenas um caminho de execução, já que
em qualquer momento há no máximo uma escolha a ser feita.
O autômato de pilha em questão reconhece exatamente e somente a linguagem w#wr.
Além disso, ele não precisa “adivinhar” o meio da cadeia, já que o símbolo # serve para
isso. As transições do estado p para o estado q indicam isso.
1.
Lewis e Papadimitriou (2000) apresentam que as operações de fecho sobre as LLC
proporcionam a construção de novas linguagens com base em linguagens previamente
conhecidas, provas, propriedades e, por fim, construindo algoritmos.
Quanto às operações sobre as LLC, considere as linguagens L1 = ｛aibicajbj | i, j ≥ 0｝ e L2
= {ambnc | m, n ≥ 0} sobre o alfabeto = {a, b, c, d} e marque a opção que melhor representa
o resultado da operação L1 ∩ L2.
Você acertou!
D.
Livre de contexto e não regular.
Para obter a resposta correta, deve-se inicialmente analisar as linguagens. Desse
modo, perceba que L1 aceita cadeias como (ab, c, cab, abcab, etc.) e tem
balanceamento duplo, o que denota uma linguagem livre de contexto.
Por outro lado, L2 aceita cadeias como ｛ac, bc, c, abc, etc.｝ e, tendo em vista que m e
n têm como regra apenas que os valores contidos sejam maiores ou iguais a 0 sem
qualquer relação entre eles, torna-se simples representar tal linguagem por um
autômato finito, tornando-a uma linguagem regular.
Note que L2 tem como subconjunto {anbnc | n ≥ 0}, que é livre de contexto, logo, isso
prova que a intersecção entre uma linguagem regular e uma linguagem livre de contexto
não é fechada sobre as linguagens regulares. No entanto, pelas propriedades de
fechamento, a intersecção de uma linguagem livre de contexto com uma linguagem
regular gera uma nova linguagem livre de contexto, mas não necessariamente regular, o
que a torna fechada a linguagens livres de contexto.
Assim, a resposta certa é: livre de contexto e não regular.
2.
A LLC correspondente ao tipo 2 da hierarquia de Chomsky tem a linguagem regular e
outras linguagens como subconjunto do seu conjunto total. Nesse tipo de linguagem,
utiliza-se o formalismo de autômato de pilha e gramática livre do contexto, o que
possibilita uma maior representação computacional se comparadaàs linguagens
regulares e tem menor poder computacional se comparada às linguagens não livres de
contexto.
Desse modo, considere a linguagem não livre de contexto La = ｛aiblcy | 2 < i < l ≤ y｝ e
assinale a alternativa que aponta corretamente qual(is) é(são) a(s) saída(s) que
representa(m) a(s) cadeia(s) dessa linguagem.
I. aaabbbbcccc
II. aaabbbbccc
III. aaaabbbbbbccccccc
IV.∈
V. aaaaaaabbbcccbbb
Resposta correta.
B.
I e III, apenas.
Análise das opções:
I. aaabbbbcccc: nesse caso, a cadeia deve ser aceita, pois há menos a's que b's, e há a
mesma quantidade de b's e c's, satifazendo as condições da linguagem para i = 3, l = 4
e y = 4.
II. aaabbbbccc: nesse caso, a cadeia deve ser rejeitada, pois há aparições iguais de a's
e c's, e há mais aparições de b's do que c's, não satisfazendo as condições da
linguagem.
III. aaaabbbbbbccccccc: nesse caso, a cadeia deve ser aceita, pois há mais b's que a's
e mais c's que b's, satifazendo as condições da linguagem para i = 4, l = 6 e y = 7.
IV. ∈: nesse caso, a cadeia deve ser rejeitada. Nas cadeias dessa linguagem não
existe cadeia vazia, pois precisaria que i = l = y = 0, não satisfazendo as condições da
linguagem, pois é necessário que, no mínimo, i > 2.
V. aaaaaaabbbcccbbb: nesse caso, a cadeia não deve ser aceita, pois a quantidade de
aparições de a’s é superior aos demais símbolos, e os b's não podem aparecer após as
aparições dos símbolos c's nessa linguagem. 
3.
O lema do bombeamento surgiu como estratégia para identificar se determinada
linguagem pertence ou não a um grupo de linguagem específico. Normalmente é atrelado
à prova por contradição, supondo características inverídicas de algum mecanismo ou
objeto para alcançar o absurdo.
Dessa forma, aplicando o lema do bombeamento, a linguagem L1 = ｛aibjck | i ≤ j ≤ k｝,
marque a opção que melhor representa a classificação da L1.
Resposta correta.
C.
Linguagem não livre de contexto.
Para chegar à resposta apropriada, é necessário aplicar o lema do bombeamento na
linguagem L1. Suponha por contradição que L1 seja uma linguagem livre de contexto e,
dessa forma, satisfaça o lema do bombeamento aplicado às linguagens livres do
contexto.
Considere p o tamanho do bombeamento e w como a cadeia apbpcp∈ L1. Se w∈ L1 e
|w| ≥ p, então, pelo lema do bombeamento, pode-se dividir w em cinco partes, de tal
forma que w = uvxyz e ∀i ≥ 0, logo, uvixyiz ∈ L1. Nessa demonstração usaremos o
bombeamento para baixo por questões didáticas.
Conforme a segunda condição do lema do bombeamento, é assegurado que v e y não
podem ser cadeias vazias. Dessa forma, considere todas as possíveis divisões de w em
duas situações.
Situação 1: se v ou y tiverem mais de um tipo de símbolo, a cadeia não terá os símbolos
na ordem correta; logo, w ∉ L1.
Situação 2: se v e y tiverem somente um tipo de símbolo do alfabeto, sabe-se então,
pela divisão da cadeia w, que pelo menos um dos tipos dos símbolos a, b ou c não vai
aparecer em v nem em y.
De acordo com o bombeamento da cadeia, com base no comprimento p, alguma das
situações (1 ou 2) vai acontecer. Dessa forma, qualquer uma das situações incorre em
contradição. Logo, pode-se dizer que L1 não é livre do contexto.
4.
LLC é um tipo de linguagem do tipo 2, e podemos afirmar que
as linguagens regulares são um subconjunto dessas. Uma das características que tornam
as linguagens livres de expressão
mais poderosas que as linguagens regulares é a possibilidade
de bombeamento duplo.
Desse modo, dado um alfabeto = ｛0, 1, 2｝ e a linguagem L1 = {2m1m0* 2n1n | m, n ≥ 0},
assinale a alternativa que aponta corretamente qual(quais) é(são) a(s) saída(s) que
representa(m) a(s) cadeia(s)
 dessa linguagem.
I. 2121
II. 12000021
III. ε
IV. 21210
V. 101
Você acertou!
C.
I e III, apenas.
Análise das opções:
I. 2121: ao considerarmos 0*, pode-se perceber que, com essa expressão, são
construídas cadeias como ｛ε, 0, 00, etc.｝. Desse modo, para uma subcadeia ε em 0* e
valor igual a 1 em m e n, tem-se 2121, o que torna a cadeia aceita.
II. 12000021: do mesmo modo, ao considerarmos 0*, pode-se admitir a cadeia 0000
como parte integrante dessa expressão. No entanto, os valores 21 estão em ordem
inversa na primeira parte da cadeia, sendo representada por 12 em vez de 21, o que
torna essa cadeia não aceita.
III. ε: para um valor m e n igual a 0 e obtendo a cadeia vazia, ε, de 0*, será produzida a
cadeia ε, o que torna a opção aceita.
IV. 21210: nesse caso, a cadeia se torna não aceita, pois não existem valores de 0's ao
final da cadeia, com exceção para um valor n = 0. No entanto, para esse caso, a
subcadeia 2121 tornaria a cadeia inválida.
V. 101: como podemos ver na expressão, nas subexpressões 2m1m e 2n1n, fica claro
que em cada uma é necessário o mesmo valor de 2’s e 1’s. Assim, nesse caso não é
possível obter cadeias apenas com valores 2’s ou 1’s, o que torna a cadeia não aceita.
5.
Contendo em seu conjunto o subconjunto das linguagens regulares e outros tipos de
linguagem, a LLC alcança o mesmo resultado quando utiliza autômato de pilha e
gramáticas livres de contexto em determinado problema.
Com base na linguagem do tipo 2 da hierarquia de Chomsky, pode-se fazer bombeamento
duplo, tanto bombeando para baixo como para cima, e, como consequência, tem-se um
poder maior de representação.
Desse modo, dado um alfabeto = ｛a, b, c｝ e a linguagem L2 = {ambmcnbm | m ≥ 0, n > 0 },
assinale a alternativa que aponta corretamente qual(quais) é(são) a(s) saída(s) que
representa(m) a(s) cadeia(s) dessa linguagem.
I. abacb
II. aabbccbb
III. c
IV. aaaabbbbcbbbb
V. aaaaaaabbbcccbbb
Resposta correta.
C.
II, III e IV, apenas.
Análise das opções:
I. abacb: nesse caso, a cadeia não deve ser aceita, pois não há possibilidade de
aparições de novos a’s depois de qualquer ocorrência dos b’s ou c’s.
II. aabbccbb: nesse caso, a cadeia deve ser aceita, pois, ao considerarmos m = 2 e n =
2, será possível alcançar a cadeia aabbccbb.
III. c: nesse caso, a cadeia deve ser aceita, pois, ao considerarmos m = 0 e n = 1, será
possível alcançar a cadeia c.
IV. aaaabbbbcbbbb: nesse caso, a cadeia deve ser aceita, pois, ao considerarmos m =
4 e n = 1, será possível alcançar a cadeia aaaabbbbcbbbb.
V. aaaaaaabbbcccbbb: nesse caso, a cadeia não deve ser aceita, pois a quantidade de
aparições de a’s deve ser igual às aparições de b’s (considerando o valor de m).
1.
O formalismo gramática livre de contexto foi desenvolvido e sistematizado inicialmente
por Avram Noam Chomsky, sendo esse mecanismo um exímio gerador das linguagens
livres de contexto ou linguagem do tipo 2, conforme a hierarquia de Chomsky. Dessa
forma, considere a gramática G1 = (｛L, K｝, {0, 1}, R, K), em que R tem as seguintes regras:
K → 1K11 | L
L → 0 L | ε
Assinale a alternativa que traduz a gramática G1 em uma linguagem livre de contexto L1.
Resposta correta.
D.
A linguagem tem a seguinte estrutura: L1 = ｛1n0m12n | n ≥ 0, m ≥ 0｝.
Observe que a linguagem pode conter cadeia vazia. Logo, pode haver a possibilidade
de não existência dos símbolos ou de algum símbolo. Note que a quantidade de 1’s
pode ser particionado em dois conjuntos: um conjunto contendo n 1’s e outro conjunto
contendo 2n 1’s. Perceba que, entre esses dois conjuntos de 1’s, pode haver aparições
de 0’s. Logo, a linguagem que gera as mesmas cadeias que a gramática G1 é a L1 = ｛
1n0m12n | n ≥ 0, m ≥ 0｝.
2.
As gramáticas livres de contexto foram desenvolvidas a partir de uma estratégia que
utiliza substituições recursivas dentro de seus símbolos denominados variáveis ou não
terminais. Em um símbolo não terminal, pode-se atribuir outro símbolo não terminal ou
um terminal.
Dessa forma, considere a linguagem L2 = ｛ 0n1m2m33n | n ≥ 0, m > 0｝ e determine as regras
usadas por essa gramática, em que será possível ver a utilização das chamadas
recursivas dentro das variáveis.
Você acertou!
E.
A gramática tem as seguintes regras: K → 0K333 | L, L → 1L22 | 12. 
Observe que a linguagem deve conter sempre a aparição dos símbolos 1 e 2, sendo
que esses símbolos devem aparecer necessariamentena mesma quantidade. Note que
os símbolos 0 e 3 podem não aparecer na cadeia, mas, quando aparecerem, a
quantidade do símbolo 3 deve ser sempre o triplo da quantidade da aparição do símbolo
0. Dessa forma, as regras são as seguintes: K → 0K333 | L, L → 1L22 | 12. De acordo
com a L2, não são possíveis as regras de formações K → 0K33 e K → 0K3333, pois, se
houver aparição dos símbolos 0 e 3, a quantidade de 3 deve ser necessariamente 3
vezes a quantidade do símbolo 0. De igual modo, nessa linguagem, não são possíveis
as regras de formação L → 21 ou L → 11.
3.
A formalização de uma ideia fornece argumentos sólidos ao se questionar sobre
determinado escopo de atuação dela, tendo, assim, a seu favor, a precisão e
notações/terminologias para se expressar melhor no tocante ao assunto. Aproveitando a
ideia de formalização, as gramáticas livres de contextos também têm a sua.
Dada a linguagem:
L3 = ｛ 1an#bn1 | n > 0｝ 
Determine a valoração de sua formalização.
Resposta correta.
C.
A 4-upla é: (｛A, B｝, {1, a, b, #}, {A → 1aBb1 , B → aBb, B → # }, A) .
Muitas gramáticas podem reconhecer a mesma linguagem, mas, levando em
consideração as alternativas apresentadas, a única que corresponde integralmente à
linguagem L3 é a A 4-upla é: (｛A, B｝, {1, a, b, #}, {A → 1aBb1 , B → aBb, B → # }, A). O
item c é a resposta correta, pois a variável inicial é a A e as variáveis são A e B,
enquanto os símbolos terminais são 1, a, b, #. Para essa questão, deve-se ter muito
cuidado nas regras de formação, no caso o conjunto R da formalização. Observe que
essa gramática não vai gerar, em nenhum momento, cadeia vazia; a sua menor cadeia
gerada é a 1a#b1, variando somente a quantidade igual de a’s e b’s. Logo, tem-se a
regra A → 1aBb1 inicialmente; em seguida, deve-se utilizar recursivamente a regra B →
aBb. Para alcançar o símbolo #, não se pode atribuir diretamente à variável A o símbolo
#, pois viabilizaria a existência da cadeia #; logo, podem-se criar as regras B → aBb, B
→ #. Observe que, nessa gramática, não existem o símbolo c, nem as regras de
formação A → Bb, A → 1Ab1 e sua variável inicial não pode ser a Z, pois esta, além de
não ser a variável que inicia a gramática, também não existe.
4. A árvore sintática é um recurso visual e uma abordagem para fazer a representação das
gramáticas livres de contexto. Com ela, pode-se ver o funcionamento das substituições
das variáveis por outras variáveis ou símbolos terminais utilizados na gramática em
questão.
Dadas as árvores sintáticas representadas nas figuras 1, 2, 3, 4 e 5, determine a gramática
que a desenha.
Você acertou!
C.
A gramática é: (｛S, L｝, {1, 0}, {S → 0S0| 1S1| L, L → 0 | 1 | ε }, S). 
Observe que a gramática gera cadeias no estilo de palíndromos de tamanhos ímpares e
pares. Note que a variável inicial é a S e as variáveis são S e L, enquanto os símbolos
terminais são 0, 1 e ε. A primeira substituição gera 0S0, mas poderia gerar, de igual
modo, a 1S1 e L, ou seja, S → 0S0| 1S1| L. A inserção da variável L é por conta do
acesso aos símbolos terminais da segunda regra, para assim, finalizar a cadeia. Logo, a
alternativa correta é: (｛S, L｝, {1, 0}, {S → 0S0| 1S1| L, L → 0 | 1 | ε }, S). Ressalta-se
que, a partir das árvores sintáticas, não são possíveis as regras S → 1S11 e L → 10. De
igual modo, essas árvores sintáticas não têm os símbolos terminais ε e #. 
5.
O problema da ambiguidade é algo indesejado em linguagens de programação, visto que
as linguagens de programação precisam trabalhar sobre um dado exato, sem dualidade
de significado, ou seja, sem ambiguidade. Por exemplo, na linguagem C, a cláusula de
condição if-then-else é bem definida e sem ambiguidade. Caso contrário, haveria
problema para o compilador entender a sintaxe da estrutura em questão.
De acordo com o conceito de ambiguidade em gramáticas livres de contexto, analise as
afirmações a seguir e assinale a alternativa que contém apenas as corretas:
I. Diz-se que uma cadeia é ambígua se tem mais de uma derivação implementável pela
gramática.
II. Diz-se que uma cadeia é ambígua se tem mais de uma árvore sintática para a derivação
de uma mesma cadeia.
III. Diz-se que uma gramática é ambígua se tem mais de uma derivação para a mesma
cadeia.
IV. Diz-se que uma árvore sintática produz cadeia ambiguamente somente se faz
derivações à esquerda.
V. O fato de uma linguagem não conseguir deixar de ser ambígua indica que se trata de
uma linguagem inerentemente mbígua.
Você acertou!
C.
II e V.
Ao analisar as afirmativas, tem-se o seguinte:
I. O fato de uma cadeia ser alcançada por mais de uma derivação não a torna ambígua,
mas multiplamente derivável.
II. A aparição de uma ambiguidade na produção de uma cadeia é provocada pela
existência de mais de uma árvore sintática na derivação da cadeia em questão.
III. O fato de uma gramática realizar mais de um tipo de derivação e alcançar a mesma
cadeia não a faz ambígua, pois é possível a existência de múltiplas derivações para
gerar a mesma cadeia e, mesmo assim, sua árvore sintática pode ser única.
IV. O fato de uma árvore ser derivável inicialmente em algum sentido não está
relacionado à geração de cadeia ambiguamente.
V. Se, ao excluir símbolos inúteis, o símbolo ε e regras do tipo Variável 1➝ Variável 2, a
ambiguidade persistir na linguagem de tal forma que não possa ser excluída, essa
linguagem é inerentemente ambígua.
1.Uma das funções de uma máquina de Turing consiste em reconhecer
linguagens. Isso quer dizer que ela é capaz de classificar palavras como
pertencentes ou não a determinada linguagem.
Considere a máquina de Turing definida a seguir:
Qual das seguintes cadeias é rejeitada pela máquina acima? 
Resposta correta.
D.
aabbaa
A linguagem aceita sobre essa máquina de Turing é L = ｛ a n b m a (n+m) | n≥1 em≥1｝ .
Ou seja, palavras que comecem com uma sequência de n símbolos ‘a’, seguidos de m
símbolos ‘b’ e terminando com (n+m) símbolos 'a'. Dentre as alternativas fornecidas, a
única palavra que não segue esse padrão é ‘aabbaa’. Para ser aceita, essa palavra
deveria terminar com 4 símbolos ‘a’. Em todos os demais casos, esse padrão se repete:
aabbbaaaaa (2 ‘a’s, 3 ‘b’s e 5 ‘a’s), abaa (1 ‘a’, 1 ‘b’ e 2 ‘a’s), aaaabaaaaa (4 ‘a’s, 1 ‘b’ e
5 ‘a’s) e abbbbaaaaa (1 ‘a’, 4 ‘b’s e 5 ‘a’s).
2. A função de transição de uma máquina de Turing é uma função parcial que
mapeia um estado e um símbolo lido na posição atual da cabeça da fita em uma
tripla que consiste no próximo estado, no símbolo que será escrito na fita e na
direção em que a cabeça da fita se moverá.
Considere a máquina de Turing dada a seguir:
 Com base no conteúdo da fita e no estado corrente da máquina, qual será o
próximo estado alcançado? O que será escrito na posição para onde a cabeça da
máquina está apontando?
Você acertou!
B.
Próximo estado: q4. Será escrito ’2’ na fita.
A combinação do estado q0 com o símbolo ‘b’ levará a máquina ao estado q4, com a
escrita do símbolo ‘2’ e movimento para a direita da cabeça da fita. As demais
transações são incorretas. A alternativa que sugere que o próximo estado é indefinido e
que a palavra seria rejeitada está incorreta, pois há uma transição válida para o par de
estado atual, com símbolo lido. As alternativas que mencionam que os próximos
estados seriam q1 ou q7 também estão incorretas, pois para ir para o estado q1 seria
necessário ler o símbolo ‘a’ na fita. Para ir para o estado q7, seria preciso ter lido o
símbolo ‘1’ ou o símbolo ‘2’ na fita. Por fim, a alternativa que acerta o próximo estado,
mas erroneamente sugere a escrita do símbolo ‘b’ na fita, está incorreta, pois essa
transação não está prevista no conjunto de transações da máquina.
3.
O estudo do que pode (ou não) ser computado é o cerne da ciência da computação.
Apesar de ser bastante antigo, ele se desenvolveu principalmente na primeira metade do
século XX e foi revolucionado quando Alan Turing propôs um formalismo genérico de
computação capaz de representar qualquer problema computável.
Avalie as seguintes afirmaçõessobre a máquina de Turing e assinale a alternativa correta. 
Você acertou!
A.
Uma máquina de Turing é capaz de reconhecer qualquer linguagem que se enquadre na
taxonomia de Chomsky.
4.
Diversas modificações para as máquinas de Turing determinística foram propostas ao
longo dos anos com o objetivo de aumentar seu poder computacional. Até hoje, todos os
modelos conseguiram no máximo igualar o poder de processamento da máquina
determinística, sem superá-lo.
Dado o gráfico de transições de uma máquina de Turing a seguir, qual é uma sequência
possível de estados percorridos para que essa máquina aceite a palavra de entrada
‘aabccb’?
Resposta correta.
C.
q0 — q0 — q2 — q2 — q2 — q4.
A única sequência que possui transições que possibilitam o reconhecimento da palavra
de entrada é q0 — q0 — q2 — q2 — q2 — q4. Veja como seriam as transições nessa
sequência de estados: iniciando em q0, ao ler a permanecer em q0, ao ler o segundo
símbolo a permanecer em q0, ao ler b ir para q2, permanecer em q2 ao ler o símbolo c,
permanecer em q2 ao ler o segundo símbolo c, e ir para o estado q4 ao ler b. Todas as
demais sequências possuem alguma transição inválida. Por exemplo, na sequência q0
q0 — q0 — q0 — q0 — q3 — q4, a última transição é inválida, pois não é possível ir de q3
para q4 lendo o valor b. Na sequência q1 — q1 — q1 — q1 — q1 — q4, o problema está
no segundo q1, pois ao ler o símbolo ‘a’, o único movimento possível é para q4. Na
sequência q0 — q2 — q2 — q2 — q2 — q4, o problema está na primeira transição para o
estado q2, que não pode ser feita com a leitura do símbolo ‘a’. Por fim, q0 — q0 — q0 —
q3 — q3 — q4 está incorreta porque a segunda transição para q3 é impossível.
5.
Uma máquina de Turing é composta de uma fita de tamanho infinito com sua cabeça de
leitura e escrita que servem de memória e como dispositivo de entrada e saída. Também
existe uma função de transição, que corresponde ao programa executado pela máquina.
Sobre a máquina de Turing, analise as seguintes afirmações:
I. Uma máquina de Turing com múltiplas fitas pode reconhecer qualquer linguagem
recursivamente enumerável.
II. Para refutar a hipótese de Church, basta apresentar uma modificação da máquina de
Turing que comprovadamente tenha mais poder computacional que uma máquina de
Turing determinística.
III. Por padrão, uma máquina de Turing determinística pode alterar diversos pontos da fita
em cada transição e é capaz de transferir sua atenção para mais de uma posição da fita
em cada argumento da função de transição.
Qual(is) dessas afirmações está(ão) correta(s)?
Resposta correta.
C.
I e II.
Somente as afirmações I e II estão corretas. A assertiva I está correta porque uma
máquina com múltiplas fitas tem o mesmo poder computacional que a máquina de
Turing tradicional; ou seja, ela reconhece as mesmas linguagens, portanto pode
reconhecer qualquer linguagem enumerável recursivamente. A assertiva II também está
correta, já que, ao encontrar um formalismo que compute uma função que não seja
computável em uma máquina de Turing, ficará provado que ela não é capaz de
computar todas as funções computáveis e que o novo formalismo possui maior poder
computacional que a máquina de Turing. A assertiva III está incorreta, pois, por padrão,
só existe uma cabeça na fita, o que significa que apenas um símbolo pode ser alterado
a cada passo da função de transição.
1.
Uma linguagem é denominada "decidível" ou "recuriva" se existe uma máquina de Turing
que a aceita e para, para cada string de entrada. A família de linguagens decidíveis é
menor do que a de linguagens recursivamente enumeráveis.
A definição de semidecisão ou semirrecursão por uma máquina de Turing é uma extensão
direta da noção de aceitação para um:
Resposta correta.
A.
autômato finito determinístico.
A definição de semidecisão por uma máquina de Turing é uma extensão direta da
noção de aceitação para o autômato finito determinístico. Um autômato finito, sempre
quando lê todas as entradas, para em um estado final ou não final. Nesse sentido, é um
dispositivo computacional útil, um algoritmo a partir do qual se pode obter respostas
confiáveis sobre se uma entrada pertence à linguagem aceita. O autômato espera até
que todas as entradas tenham sido lidas e observa o estado da máquina. Na máquina
de Turing de semidecisão, uma linguagem L não pode ser empregada de maneira útil
para dizer se uma string w está em L, porque, se w não pertence a L, então nunca se
sabe se a máquina não vai entrar em loop.
2.
As gramáticas irrestritas geram linguagens recursivamente enumeráveis. As produções
da gramática irrestrita não têm restrições, gerando linguagens que precisam ser
reconhecidas por uma máquina de Turing.
Qual alternativa representa uma gramática irrestrita e suas regras de produção, geradas
por determinada linguagem recursivamente enumerável e reconhecidas pelo autômato de
Turing?
Resposta correta.
D.
G = (｛S, X, Y｝, {a, b, c}, P, S)
P = {
S → aXb | aXa
Xa → c
Xb → c
X → ε
}
Para a explicação, considere a gramática: G = (V, Σ, P, S).
Gramáticas do tipo 3, pois geram linguagens regulares. As gramáticas do tipo 3 devem
ter um único elemento não terminal no lado esquerdo e um do lado direito consistindo
produções no seguinte formato: α∈ N , β∈ Σ, β∈ N, β∈ ΣN ou β = ε, de forma não
exclusiva.
Gramáticas do tipo 2 geram linguagens livres de contexto. As produções devem estar
na forma: α∈ N, β∈ V*.
A gramática do tipo 1 gera linguagens sensíveis ao contexto. As produções devem estar
no formato: α∈ V*NV*, β∈ V* , |β| ≥ |α|.
 A alternativa correta é a que representa uma gramática do tipo 0, que gera linguagens
recursivamente enumeráveis. As produções não têm restrições. Essa linguagem é que
é reconhecida por uma máquina de Turing. As produções devem estar no formato: α∈
V*NV*, β∈ V*.
3.
Seja L uma linguagem.
Qual da(s) alternativa(s) está(ão) correta(s) com base na teoria de linguagem
recursivamente enumerável?
I. Nem L, nem o complemento de L, são linguagens recursivamente enumeráveis.
II. Se L é recursivamente enumerável, o complemento de L pode não ser recursivamnte
enumerável, e vice-versa.
III. L e o complemento de L são recursivamente enumeráveis, mas não são recursivos.
IV. L e o complemento de L são recursivos.
Você acertou!
E.
Apenas as alternativas I, II e IV estão corretas; as demais estão incorretas.
A alternativa I está correta, porque se L não for recursivamente enumerável, seu
complemento não será recursivamente enumerável.
A alternativa II está correta, porque se L for recursivamente enumerável, o complemento
de L não precisa ser recursivamente enumerável, ou vice-versa. As linguagens
recursivamente enumeráveis não são fechadas sob complementação. A alternativa III
está incorreta, porque se L for recursivamente enumerável, o complemento de L não
será recursivamente enumerável. Mas, se L é recursivo, o complemento de L também
será recursivo, e ambos serão recursivamente enumeráveis, porque as linguagens
recursivas são um subconjunto das recursivamente enumeráveis. A alternativa IV está
correta, porque se L for recursivo, o complemento de L também será recursivo.
4.
Uma linguagem L é recursiva se alguma máquina de Turing (MT) aceitar e parar a cada
entrada.
O complemento de uma linguagem recursiva também é recursivo. Se L é recursivo,
consequentemente:
Você acertou!
A.
L é recursivamente enumerável.
Uma máquina de Turing aceita uma string w se a MT parar em um estado final. Uma
máquina de Turing rejeita uma string w se a MT parar em um estado não final ou se a
MT nunca parar. Uma linguagem L é recursivamente enumerável se alguma MT a
aceitar. Uma linguagem L é recursiva se alguma MT a aceitar e parar a cada entrada. L
ser recursiva implica L recursivamente enumerável.
5.
Existe a prova que faz uso do seguinte fato: u ma linguagem recursivamente enumerável
pode ser aceita ou reconhecida pela máquina de Turing.
Sobre essa afirmação, é possível dizer:
Resposta correta.
B.
Existe a prova, que diz: um conjunto de strings é um conjunto infinito econtável.
Algumas linguagens não são recursivamente enumeráveis.
Prova: um conjunto de strings é um conjunto infinito e contável.
O conjunto de linguagens é infinito porque é um conjunto de possibilidades de strings a
serem passadas pelos usuários.
Linguagens recursivamente enumeráveis são contáveis porque as máquinas de Turing
são contáveis.
1. A classe das linguagens recursivas está contida no grupo das linguagens
recursivamente enumeráveis e costuma ser denotada por meio das
máquinas de Turing, como no exemplo a seguir. Tais máquinas, ao denotar
linguagens recursivas, têm uma característica muito importante, isto é,
sempre param, aceitando determinada cadeia ou rejeitando-a. Por esse
motivo, essas linguagens são comumente chamadas de decidíveis ou
Turing decidíveis.
Dada a máquina de Turing apresentada, considere as cadeias a seguir e, posteriormente,
assinale a alternativa que contém as aceitas por ela.
I - abc
II - aabcaab
III - acac
IV - aca
V - aacaac
Resposta correta.
C.
II e IV.
- abc: inicia o processo no estado q0, onde transita para o estado q1 e, posteriormente,
para q2, onde o processo para, negando a cadeia.
- aabcaab: inicia no estado q0, passando ao estado q1, q2, q3, q4, voltando ao estado
q0, onde o processo é repetido até chegar novamente a q0. Ao chegar em q0, transita
para q7, q8, q9 e q10, q0 e q5 para, finalmente, parar em um estado de aceitação.
- acac: inicia em q0, passa para q1, q2, q3, q4 até voltar à q0, onde vai a q5, no qual o
processo para, negando a cadeia.
- aca: inicia em q0, passa por q1, q2, q3 e q4. Ao chegar novamente em q0, vai a q5 e
finaliza em q6, aceitando a cadeia.
- aacaac: percorre do estado q0 a q4 duas vezes, volta à q0, passa a q5, onde o
processo para, negando a cadeia.
2 .Conforme Coutinho (2007), a classe das linguagens recursivas é fechada sobre
as operações de união, interseção e complementação. Isso significa que, dadas
duas linguagens recursivas L1 e L2, ao aplicar qualquer uma dessas operações, o
resultado consistirá em uma linguagem também recursiva.
Dado o exposto, considere
Resposta correta.
D.
aabbaabb, bbbbbb, aaaaaaaa, aabaab.
3. Conforme Menezes (2011), as linguagens recursivas englobam, do maior nível
de poder para o menor, as linguagens próprias, os conjuntos das linguagens
sensíveis ao contexto, as linguagens livres de contexto e, por fim, as linguagens
regulares.
As linguagens regulares podem ser representadas por expressões regulares. Desse
modo, dada a máquina Turing a seguir, marque a opção que representa a expressão
regular que a denota. 
Resposta correta.
D.
1*00*10(10)*
0*1*(0+1): note que essa expressão pode produzir a cadeia 11, que não é aceita pela
máquina de Turing apresentada.
(0+1)*0101: essa expressão pode produzir a cadeia 0101, que não é aceita pela
máquina de Turing.
(0+1)*101: de forma semelhante à opção anterior, essa expressão pode produzir a
cadeia 0101, que não é aceita pela máquina de Turing.
1*00*10(10)*: essa opção produz 1* (estado q1), 0, na transição do estado q1 para q2,
0* no estado q2, 1, na transição do estado q2 para q3, 0, na transição de q3 a q4 e, por
fim, (10)* nas transições de q4 para q3 e de q3 para q4.
01(010)*: essa expressão pode produzir a cadeia 01, que é rejeitada pela máquina de
Turing.
4.
Conforme Rich (2019), para toda cadeia w pertencente a Σ*,
dada uma linguagem L, se existir, ao menos, uma máquina
de Turing que represente L de modo a parar, aceitando ou
 negando w, dizemos que L é uma linguagem recursiva.
Tendo em vista o exposto, dada a linguagem L= ｛ai bj ck | i × j = k; i, j, k ≥ 1｝, analise as
opções a seguir e informe quais representam as cadeias válidas para L.
 
I - abcc
II - aabbcccc
III - aaaa
IV - aaabbcccccc
V - abbccc
Resposta correta.
B.
II e IV.
Perceba que i representa a quantidade de símbolos a’s, j de b’s e k de c’s.
As restrições são que i × j=k e que i,j,k ≥1.
- abcc: i = 1, j = 1 k = 2, pois 1 × 1 ≠ 2.
- aabbcccc: i = 2, j = 2 k = 4, temos 2 × 2 = 4.
- aaaa: essa alternativa anula a regra 2, i,j,k ≥1.
- aaabbcccccc: i = 3, j = 2 k = 6, tem-se 3 × 2 = 6.
- abbccc: : i = 1, j = 2 k = 3, tem-se 1 × 2 ≠ 3.
5. Conforme Sipser (2005), provar que uma linguagem é recursiva é simples. Basta
elaborar uma máquina de Turing que a decida. Por isso, normalmente conhecemos
essas linguagens com denominações como Turing decidíveis ou, simplesmente,
decidíveis. Desse modo, ao ler qualquer cadeia w, a máquina deve simplesmente
aceitá-la se fizer parte da linguagem ou recusá-la caso contrário.
Diante do exposto, considere a máquina de Turing a seguir e informe qual linguagem
recursiva sobre ｛0｝ ela denota. 
Resposta correta.
A.
L1 = ｛02^n) | n ≥ 0｝
1.
Uma linguagem finita é aquela que corresponde a um conjunto finito de cadeias de
caracteres. Logo, uma linguagem não é finita se existir um conjunto infinito de cadeias de
caracteres nessa linguagem. Todas as linguagens finitas são regulares, mas nem todas
as regulares são finitas. Uma linguagem regular é aquela que pode ser expressa por uma
expressão regular. Uma expressão regular consiste de sequências de caracteres que
podem ter: (a) repetições de determinadas subsequências em indeterminado número de
vezes e; (b) escolhas entre duas ou mais subsequências.
Todas as linguagens regulares são livres de contexto, mas nem todas as livres de
contexto são regulares. Uma linguagem livre de contexto é aquela que pode ser expressa
por meio de uma gramática livre de contexto. Uma gramática livre de contexto é um
conjunto de regras de derivação recursivas aninhadas além daquilo que as linguagens
regulares já são capazes de reconhecer. Cada regra, denominada "produção", é definida
como a forma como um símbolo não terminal pode ser expandido em uma sequência de
símbolos terminais e não terminais. A cadeia de caracteres a ser reconhecida ou gerada
por uma gramática livre de contexto consiste apenas de símbolos terminais, sendo os
símbolos não terminais usados apenas nas etapas intermediárias de geração ou
reconhecimento da cadeia de caracteres.
Todas as linguagens livres de contexto são sensíveis ao contexto, mas nem todas as
sensíveis ao contexto são livres de contexto. Uma linguagem sensível ao contexto é
aquela que pode ser expressa por alguma gramática sensível ao contexto. Uma gramática
sensível ao contexto é um tanto similar a uma gramática livre de contexto, mas com uma
grande diferença: as produções não necessariamente mapeiam apenas símbolos não
terminais para sequências de terminais e não terminais. Elas podem mapear sequências
de terminais e não terminais para outras sequências de terminais e não terminais, e essa
característica as torna mais expressivas do que as gramáticas livres de contexto. A única
restrição de uma gramática sensível ao contexto é que a quantidade de símbolos no lado
esquerdo das suas produções deve ser menor ou igual à quantidade de símbolos no lado
direito.
Todas as linguagens sensíveis ao contexto são irrestritas, mas nem todas as irrestritas
são sensíveis ao contexto. A palavra "irrestrita" já diz que a linguagem não impõe
nenhuma restrição às suas produções gramaticais. Esse conjunto engloba as linguagens
chamadas "recursivamente enumeráveis".
Considere a gramática a seguir para gerar a linguagem:
｛ anbncn : n ≥ 1 ｝
S → aBC
S → aSBC
CB → CZ
CZ → WZ
WZ → WC
WC → BC
aB → ab
bB → bb
bC → bc
 cC → cc
Como a linguagem reconhecida por essa gramática pode ser classificada segundo a
definição apresentada? Considere apenas a categoria mais restrita a que essa gramática
pertence.
Você acertou!
C.
Linguagem sensível ao contexto.
A gramática proposta fere as restrições para as linguagens finitas, pois permite
reconhecer um número ilimitado de palavras. Ela também não é regular, pois determina
que a quantidade de símbolos a, b e c seja igual, o que não pode ser feito nesse tipo de
linguagem. A gramática proposta também não é livre de contexto, pois suas produções
admitem mais do que apenas um símbolo não terminal no lado esquerdo das