Logo Passei Direto
Buscar

Teoria da Computação

Colégio Objetivo
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.
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
a) II, IV e V, apenas
b) III, IV e V, apenas
c) II, III e IV, apenas.
d) I, III e V, apenas.
e) I, III e IV, apenas
User badge image
Estudando com Questões

ano passado

User badge image
Estudando com Questões

ano passado

Prova Linguagens Formais e Autômatos
5 pág.

Prova Linguagens Formais e Autômatos

IESB

Respostas

User badge image

Ed Verified user icon

ano passado

Vamos analisar a linguagem L2 = {a^m b^m c^n b^m | m ≥ 0, n > 0}. Isso significa que para cada 'a' que aparece, deve haver um 'b' correspondente, e depois deve haver um número de 'c's (pelo menos um) seguido pelo mesmo número de 'b's que foi usado antes. Agora, vamos verificar cada uma das opções: I. abacb - Aqui temos 1 'a', 1 'b', 1 'c' e 1 'b' novamente. Isso se encaixa na forma da linguagem, então está correto. II. aabbccbb - Aqui temos 2 'a's, 2 'b's, 2 'c's e 2 'b's novamente. Isso também se encaixa na forma da linguagem, então está correto. III. c - Aqui temos apenas 'c', sem 'a' ou 'b'. Como a condição exige pelo menos um 'b' e um 'a', isso não se encaixa na linguagem. Portanto, está incorreto. IV. aaaabbbbcbbbb - Aqui temos 4 'a's, 4 'b's, 4 'c's e 4 'b's novamente. Isso se encaixa na forma da linguagem, então está correto. V. aaaaaaabbbcccbbb - Aqui temos 6 'a's, 3 'b's, 3 'c's e 3 'b's novamente. Isso não se encaixa na forma da linguagem, pois o número de 'b's não corresponde ao número de 'a's. Portanto, está incorreto. Agora, vamos compilar as informações: - I: Correto - II: Correto - III: Incorreto - IV: Correto - V: Incorreto As alternativas corretas são I, II e IV. Portanto, a alternativa que contém todos os itens verdadeiros é: a) II, IV e V, apenas.

Essa resposta te ajudou?

0
Dislike0

Ainda não achou a resposta?

  • Integrado com os principais modelos de IA do mercado
  • Respostas em segundos
  • IA treinada para estudantes brasileiros.
PasseIA logoEvolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Prova Linguagens Formais e Autômatos
5 pág.

Prova Linguagens Formais e Autômatos

IESB

Mais perguntas desse material

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.
a) Linguagem regular.
b) Livre de contexto e não regular.
c) Livre de contexto e regular.
d) Linguagem não livre de contexto.
e) Linguagem não livre de contexto, mas regular.

Uma gramática irrestrita é definida como aquela em que nenhuma restrição adicional é aplicada às suas regras de produção. Note que as linguagens regulares, as livres de contexto e as sensíveis ao contexto são casos particulares das linguagens irrestritas.
Qual das alternativas a seguir apresenta uma linguagem que pode ser classificada apenas como irrestrita na hierarquia de Chomsky?
a) S → aSa, S → bSb, S → ε
b) S → aAbba, aAb → aabbbA | ab, bAb → bbA, bAa → Bbaa, bB → Bb, aB → aA
c) S → aS, S → bA, A → ε, A → cA
d) S → SS, S → (S), S → ()
e) S → aSBC, S → aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc

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
A) II e IV.
B) I e III.
C) III e V.
D) II e V.
E) I e IV.

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.
Dito isso, considere a gramática linear unitária à esquerda (GLUE) apresentada e marque a alternativa que representa a expressão regular equivalente.
A) acb + ab*ab + bca.
B) acab + acc*b + bca.
C) acb + ac*ab + bca.
D) ac*b + acbac + bca.
E) ac*b + ac*ba + bca.

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) É a capacidade que um autômato finito tem de chegar a dois estados diferentes por meio da transição espontânea épsilon, sendo essa transição determinante no estado de aceitação.
b) É a capacidade que um autômato finito com estado finito tem de assegurar que pode ou não utilizar um símbolo, ficando a cargo do estado não consumir todos os símbolos do alfabeto, sendo o consumo dos símbolos optativo.
c) É a capacidade que um autômato com estados finitos e predefinidos estabelece a partir de seus estados iniciais de alcançar o único estado de aceitação possível, caracterizando o determinismo.
d) É 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 expresso por meio da quíntupla da formalização.
e) É a capacidade que um autômato finito tem de realizar sua computação na função programa por meio de três estados iniciais e dois estados de aceitação, sendo esta a quantidade mínima de estados apropriados.

Matheus está estudando sobre linguagens formais, mais especificamente sobre a hierarquia de Chomsky. Ao se deparar com a gramática: S → ISaaF | aa, Sa → aaS, aSF → BaF | a, aB → Ba, IB → IS, Ia → a.
Matheus classificou-a como uma gramática sensível ao contexto. Sobre isso, é possível afirmar que:
A) Matheus está correto.
B) Matheus está errado, pois essa gramática é classificada como regular.
C) Matheus está errado, pois essa gramática é classificada como irrestrita.
D) Matheus está errado, pois essa gramática é classificada como sensível ao contexto.
E) Matheus está errado, pois essa gramática é classificada como livre de contexto.

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.
A) Linguagem não livre de contexto.
B) Livre de contexto e não regular.
C) Linguagem regular.
D) Livre de contexto e regular.
E) Linguagem regular não determinística.

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.
A) A 4-upla é: ({A, B}, {1, a, b}, {A → 1aAb, A → B, B → # }, Z).
B) A 4-upla é: ({A, B}, {1, a, b, c}, {A → 1aAb1 , A → B, B → # }, A).
C) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aAb1 , A → Bb, B → # }, A).
D) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1Ab1 , A → B, B → # }, A).
E) A 4-upla é: ({A, B}, {1, a, b, #}, {A → 1aBb1 , B → aBb, B → # }, A).

Mais conteúdos dessa disciplina