Enunciados de questões e informações de concursos
#2171839 FUNDATEC - 2022 - Pós-Graduação em Computação (SBC)
Sobre o lema do bombeamento para as linguagens regulares, analise as assertivas a seguir:
I. Se uma linguagem é Regular, então é aceita por um Autômato Finito Determinístico o qual possui um número finito e predefinido de n estados.
II. Se o autômato reconhece uma entrada w de comprimento maior ou igual a n, obrigatoriamente o autômato assume algum estado q mais de uma vez, então existe um ciclo na função programa que passa por q.
III. A entrada w pode ser dividida em 3 subpalavras w = xyz tal que |xy| <= n, |y| >= 1 e onde y é a parte de w reconhecida pelo ciclo na função programa.
IV. O Lema do bombeamento não pode ser utilizado para provar que uma determinada linguagem é Não Regular.
Quais estão corretas?
Outras questões do mesmo concurso: SBC / POSCOMP (SBC) / 2022
