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.

No contexto da Teoria da Computação, os autômatos finitos são modelos formais utilizados para o reconhecimento de linguagens regulares. O Autômato Finito Determinístico (AFD) e o Autômato Finito Não Determinístico (AFN) distinguem-se principalmente quanto à definição e ao comportamento da função de transição δ. Com base nas definições formais desses modelos, informe se é verdadeiro (V) ou falso (F) o que se afirma a seguir e assinale a alternativa com a sequência correta.
( ) Em um AFD, são permitidas transições vazias (ε) que possibilitam a mudança de estado sem o consumo de símbolos da entrada. ( ) Formalmente, no AFD, a função de transição pode ser representada por δ: Q × Σ → Q. ( ) Em um AFN, o processamento de uma cadeia pode ocorrer por múltiplos caminhos de execução possíveis a partir de um mesmo estado e símbolo de entrada. ( ) No AFN, a função de transição pode ser formalmente representada por δ: Q × Σ → P(Q).

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).