Na Teoria da Computação, a Tese de Church-Turing estabelece uma relação entre o conceito intuitivo de algoritmo e modelos formais de computação, como a Máquina de Turing. Embora não seja um teorema formalmente demonstrado, é amplamente aceita como uma hipótese sobre os limites do que pode ser computado. Com base nessa concepção, assinale a alternativa que expressa corretamente o conteúdo da Tese de Church-Turing.

Um Professor do IFCE, ao ministrar Compiladores, propõe que os alunos desenvolvam um compilador simplificado. Em uma das etapas, devem percorrer o código-fonte caractere por caractere, identificar padrões (palavras reservadas, identificadores, operadores e constantes) e organizá-los em unidades estruturadas, podendo utilizar expressões regulares e autômatos finitos.
Considerando as fases clássicas da compilação, essa etapa é denominada

Na teoria das linguagens formais, a Hierarquia de Chomsky classifica as linguagens em quatro tipos (0, 1, 2 e 3), de acordo com seu poder de geração e o modelo computacional capaz de reconhecê-las. Considerando essa classificação, as linguagens livres de contexto, pertencentes ao Tipo 2 da hierarquia, são reconhecidas por qual dos seguintes modelos computacionais?

No contexto da teoria da computação, qual é a característica fundamental que define uma linguagem regular? 

Os autômatos finitos são amplamente utilizados na computação devido à sua simplicidade e eficiência para resolver problemas que envolvem o reconhecimento de padrões e a manipulação de cadeias de caracteres. Sobre autômatos finitos, considere as seguintes afirmações:

I - A máquina de estados de um autômato finito, também denominada controle finito, é definida pelo conjunto de estados e pela função de transição.

II - Uma cadeia de entrada é aceita por um autômato quando, após esgotamento da cadeia, o estado corrente do autômato é do tipo final.

III - Estados inacessíveis são aqueles para os quais não existe no autômato qualquer caminho, formado por transições válidas, que permita atingi-los a partir do estado inicial do autômato. 

IV - Uma das características dos autômatos finitos é a existência de memória auxiliar.

Assinale a alternativa que apresenta apenas afirmações corretas:

A teoria dos autômatos é uma área da ciência da computação que utiliza conceitos matemáticos para estudar modelos abstratos de máquinas computacionais. Considere os tipos de autômatos e suas capacidades. Qual das afirmativas abaixo é correta?

Analise este autômato concebido no software JFLAP a seguir.

A única cadeia de caracteres aceita pelo autômato acima é:

Dado o autômato Finito abaixo, assinale a alternativa onde a expressão regular (ER) o representa:

O autômato finito determinístico

Dada a expressão regular

(^[0-9]$|^9[1-8]?$|^2[0-9]{2}$),

assinale a alternativa que satisfaz essa expressão. 

Considere um autômato não determinístico NFA ܰN = (Q, ∑, δ, a, F), onde Q = {a, b, c, d, e, g} representa os estados, ∑ = {0,1} é o alfabeto, δ é a função de transição, ܽa é o estado inicial e F = {c, ƒ} os estados de aceitação, representados pelo diagrama a seguir

                                                   

A linguagem desse autômato pode ser descrita como 

Leia os itens contendo as expressões regulares que poderão ser associadas ao autômato da figura, conforme aquilo que a bibliografia adotada descreve sobre autômatos finitos e expressões regulares.

I) A expressão regular 0*1(1+00*1)* representa o automato da figura.

II) A expressão regular 0*1*1+11*0*1 representa o automato da figura.

III) A expressão regular (0+1)*1 representa o automato da figura.

Assinale somente a alternativa que apresenta todas as afirmativas CORRETAS.

Considerando-se a definição autômatos finitos, assinale a única alternativa que contém somente cadeias de caracteres totalmente aceitas pelo autômato finito da figura.

Considerando-se a definição sobre autômatos finitos e linguagens, assinale a única alternativa que contém a disposição correta (da esquerda para a direita) dos tipos de gramática segundo o critério da abrangência das linguagens geradas (gramática mencionada gera linguagem que abrange a linguagem gerada pela gramática a sua direita – hierarquia de Chomsky).