Logo Passei Direto
Buscar
A Hierarquia de Chomsky classifica as linguagens formais em quatro tipos, conforme as restrições aplicadas às regras de produção. Essa classificação determina o grau de expressividade e a complexidade computacional de cada tipo gramatical, sendo base para a construção de compiladores, analisadores sintáticos e interpretadores. SOUSA, Carlos E B.; NASCIMENTO, Leonardo B G.; MARTINS, Rafael L.; et al. Linguagens Formais e Autômatos. Porto Alegre: SAGAH, 2021. E-book. p.Capa. ISBN 9786556901138. Disponível em: https://app.minhabiblioteca.com.br/reader/books/9786556901138/ . Acesso em: 10 jun. 2025. Com base nessa estrutura teórica, avalie as afirmativas a seguir: I. As linguagens sensíveis ao contexto aceitam regras onde o lado direito da produção pode ter menos símbolos do que o lado esquerdo, permitindo maior flexibilidade na contração de cadeias. II. As gramáticas regulares possibilitam regras com dois ou mais não-terminais no lado esquerdo, desde que o lado direito tenha apenas terminais organizados linearmente. III. As gramáticas livres de contexto utilizam regras com exatamente um símbolo não-terminal no lado esquerdo e qualquer sequência de símbolos no lado direito. IV. A estrutura da hierarquia L₃ ⊂ L₂ ⊂ L₁ ⊂ L₀ indica que todas as linguagens regulares também pertencem às classes superiores, mantendo as relações de inclusão estrita.
User badge image
Felipe Duarte

anteontem

Respostas

User badge image

Ed Verified user icon

anteontem

Vamos analisar cada afirmativa: I. As linguagens sensíveis ao contexto aceitam regras onde o lado direito da produção pode ter menos símbolos do que o lado esquerdo, permitindo maior flexibilidade na contração de cadeias. Falso. Em gramáticas sensíveis ao contexto, o lado direito deve ter pelo menos o mesmo número de símbolos que o lado esquerdo, não menos. II. As gramáticas regulares possibilitam regras com dois ou mais não-terminais no lado esquerdo, desde que o lado direito tenha apenas terminais organizados linearmente. Falso. As gramáticas regulares têm regras que permitem apenas um não-terminal no lado esquerdo e o lado direito pode ter um terminal ou um terminal seguido de um não-terminal. III. As gramáticas livres de contexto utilizam regras com exatamente um símbolo não-terminal no lado esquerdo e qualquer sequência de símbolos no lado direito. Verdadeiro. Essa afirmativa está correta, pois define corretamente as gramáticas livres de contexto. IV. A estrutura da hierarquia L₃ ⊂ L₂ ⊂ L₁ ⊂ L₀ indica que todas as linguagens regulares também pertencem às classes superiores, mantendo as relações de inclusão estrita. Verdadeiro. Essa afirmativa está correta, pois reflete a hierarquia de Chomsky, onde as linguagens regulares (L₃) estão contidas nas linguagens livres de contexto (L₂), que estão contidas nas linguagens sensíveis ao contexto (L₁), que por sua vez estão contidas nas linguagens recursivamente enumeráveis (L₀). Com base nas análises, os itens verdadeiros são III e IV. Portanto, a alternativa que contém todos os itens verdadeiros é: d) III e IV.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

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

Mais conteúdos dessa disciplina