Question

Sabe-se que toda expressão regular descreve uma linguagem regular, que autômatos finitos, determinísticos ou não, reconhecem linguagens regulares. Além disso, temos o fato que gramáticas regulares geram linguagens regulares. Sabemos também que linguagens regulares são fechadas para operações booleanas (união, interseção e complemento) entre conjuntos.

Com base no texto acima e nos conhecimentos adquiridos no curso, assinale a alternativa verdadeira:

Escolha uma:
a. Toda linguagem infinita possui uma expressão regular que a descreve.
b. Se e são expressões regulares, então + especifica uma linguagem que é finita, se e somente se, for subconjunto de e for finita.
c. Existe uma linguagem finita que não possui expressão regular que a descreve.
d. Toda linguagem aceita por AFND é descrita por uma expressão regular não-determinística.
e. Existem linguagens descritas por expressão regular que não possuem reconhecedores capazes de reconhece-las em tempo linear no tamanho da cadeia de entrada.

Answer 1

b. Se  e são expressões regulares, então + especifica uma linguagem que é finita, se e somente se,  for subconjunto de  e  for finita. 

Answer 2

b. Se  e são expressões regulares, então + especifica uma linguagem que é finita, se e somente se,  for subconjunto de  e  for finita.