Alternativa correta: A - I, e II, apenas

A questão aborda o conceito de linguagem regular e sua relação com autômatos finitos e expressões regulares. É importante para o cargo de Professor ter um entendimento claro sobre linguagens formais e autômatos, pois esses são conceitos fundamentais em teoria da computação e ensino de disciplinas relacionadas.

Resumo teórico:

Uma linguagem regular é um conjunto de cadeias (ou palavras) que pode ser reconhecido por um autômato finito, seja ele determinístico (DFA) ou não determinístico (NFA). Essas linguagens também podem ser descritas por expressões regulares. As linguagens regulares são um subconjunto das linguagens livres de contexto, que são, por sua vez, reconhecíveis por autômatos de pilha.

Análise das afirmações:

I. L é uma linguagem regular.

Correto. A linguagem L, que consiste em palavras binárias com um número par de 1s, é uma linguagem regular. Isso ocorre porque é possível construir um autômato finito que verifica se o número de 1s é par, alternando entre dois estados (um para par e outro para ímpar) conforme lemos cada 1. Portanto, a afirmação I é verdadeira.

II. É possível construir um autômato finito determinístico (DFA) que reconhece a linguagem L.

Correto. Como mencionado acima, um autômato finito, especificamente um DFA, pode ser construído para reconhecer palavras com um número par de 1s. Ele alterna entre estados conforme vai lendo os dígitos da palavra, validando assim a linguagem L. Logo, a afirmação II é verdadeira.

III. A linguagem L não pode ser denotada por uma expressão regular.

Incorreto. Qualquer linguagem regular pode ser descrita por uma expressão regular. Portanto, a afirmação de que L não pode ser denotada por uma expressão regular é falsa.

IV. A linguagem L pertence à classe de linguagens livres de contexto, mas não à classe de linguagens regulares.

Incorreto. Embora L pertença à classe de linguagens livres de contexto (pois todas as linguagens regulares são também livres de contexto), a afirmação de que não é regular está errada. Como já discutido, L é uma linguagem regular. Portanto, a afirmação IV é falsa.

Com base nas explicações acima, a alternativa correta é a A - I, e II, apenas.

Gostou do comentário? Deixe sua avaliação aqui embaixo!