itc - itc

Question 1

O que é um alfabeto em teoria da computação?

Answer 1

Um conjunto finito e não vazio de símbolos.

Question 2

O que é uma cadeia?

Answer 2

Uma sequência de símbolos de um alfabeto.

Question 3

Como se denota a cadeia vazia?

Answer 3

Por ε ou λ.

Question 4

O que é o comprimento de uma cadeia?

Answer 4

O número de símbolos que a cadeia contém.

Question 5

O que é o reverso de uma cadeia?

Answer 5

A cadeia escrita na ordem inversa.

Question 6

O que é uma subcadeia?

Answer 6

Uma sequência de símbolos que aparece dentro de outra cadeia.

Question 7

O que é concatenação de cadeias?

Answer 7

A união de duas cadeias, colocando uma após a outra.

Question 8

O que é a potência de uma cadeia?

Answer 8

A concatenação da mesma cadeia várias vezes.

Question 9

O que é o Fecho de Kleene (Σ*)?

Answer 9

O conjunto de todas as cadeias possíveis sobre o alfabeto Σ.

Question 10

O que é uma linguagem em teoria da computação?

Answer 10

Um conjunto de cadeias (finito ou infinito) que é um subconjunto de Σ*.

Question 11

Quais são os componentes de um autômato finito?

Answer 11

Estados, alfabeto de entrada, função de transição, estado inicial, e conjunto de estados de aceitação.

Question 12

O que são estados de aceitação em um autômato finito?

Answer 12

Estados nos quais, se o autômato termina o processamento da cadeia de entrada, a cadeia é aceita.

Question 13

O que é a função de transição em um autômato finito?

Answer 13

Uma função que define para cada par (estado atual, símbolo de entrada) o próximo estado.

Question 14

O que é a linguagem reconhecida por um autômato finito?

Answer 14

O conjunto de cadeias que o autômato aceita.

Question 15

Qual é a diferença entre um autômato finito determinístico (DFA) e um não determinístico (NFA)?

Answer 15

Em um DFA, cada par (estado, símbolo) leva a um único próximo estado, enquanto em um NFA, pode haver múltiplas transições para o mesmo par.

Question 16

Dê um exemplo de aplicação prática de um autômato finito.

Answer 16

Um controlador de portas que muda de estado (aberto/fechado) com base em sinais de entrada (frente/atrás/ambos/nenhum).

Question 17

O que cada símbolo da 5-tupla (Q, Σ, δ, q0, F) representa?

Answer 17

Q é o conjunto de estados<br></br>Σ é o alfabeto de entrada<br></br>δ é a função de transição<br></br>q0 é o estado inicial<br></br> F é o conjunto de estados de aceitação.

Question 18

O que é um autômato finito?

Answer 18

Um autômato finito é um modelo matemático de computação que realiza operações em uma sequência de entradas, mudando entre estados de acordo com uma função de transição.

Question 19

Qual é a definição formal de um autômato finito?

Answer 19

Um autômato finito é definido por uma quíntupla M = (Q, Σ, δ, q0, F), onde Q é o conjunto de estados, Σ é o alfabeto de entrada, δ é a função de transição, q0 é o estado inicial, e F é o conjunto de estados de aceitação.

Question 20

O que é a operação módulo em matemática?

Answer 20

A operação módulo retorna o resto de uma divisão entre dois inteiros. Dados a e b inteiros positivos, a mod b é o resto da divisão de a por b.

Question 21

Como um autômato finito processa uma cadeia de entrada?

Answer 21

Um autômato finito processa uma cadeia de entrada começando no estado inicial e mudando de estado conforme cada símbolo da cadeia é lido, de acordo com a função de transição. Se, ao final da leitura, o autômato está em um estado de aceitação, a cadeia é aceita

Question 22

O que significa dizer que uma linguagem é regular?

Answer 22

Uma linguagem é regular se existe um autômato finito que a reconhece, ou seja, que aceita todas as cadeias pertencentes à linguagem e rejeita todas as outras.

Question 23

Quais são as operações regulares que podem ser aplicadas às linguagens regulares?

Answer 23

As operações regulares incluem união, concatenação e estrela (fechamento de Kleene).

Question 24

O que significa a operação de união de linguagens regulares?

Answer 24

A operação de união de linguagens regulares, denotada por A ∪ B, resulta em uma nova linguagem que contém todas as cadeias que pertencem a A ou B (ou ambas).

Question 25

O que significa a operação de concatenação de linguagens regulares?

Answer 25

A operação de concatenação de linguagens regulares, denotada por A ° B, resulta em uma nova linguagem formada pela concatenação de uma cadeia de A com uma cadeia de B.

Question 26

O que é a operação estrela (fechamento de Kleene) de uma linguagem regular?

Answer 26

A operação estrela, denotada por A*, resulta em uma nova linguagem formada por zero ou mais concatenações de cadeias de A.

Question 27

O que significa dizer que a classe das linguagens regulares é fechada sob uma operação?

Answer 27

A classe das linguagens regulares é fechada sob uma operação se, ao aplicar essa operação a linguagens regulares, o resultado também é uma linguagem regular.

Question 28

Qual a importância das definições formais na teoria da computação?

Answer 28

As definições formais são importantes na teoria da computação porque evitam ambiguidades e permitem a análise rigorosa e a prova de propriedades das linguagens e dos autômatos.

Question 29

Qual é a função de transição em um autômato finito?

Answer 29

A função de transição δ determina como o autômato muda de estado para estado com base no símbolo de entrada atual. Ela é uma função que mapeia um estado e um símbolo de entrada para um novo estado.

Question 30

O que significa que um autômato é determinístico?

Answer 30

Um autômato é determinístico (DFA) se, para cada estado e símbolo de entrada, existe exatamente uma transição definida, ou seja, a função de transição é uma função total.

Question 31

O que é um autômato não-determinístico?

Answer 31

Um autômato não-determinístico (NFA) é um autômato onde, para um estado e símbolo de entrada, pode haver várias transições possíveis, incluindo a possibilidade de transições sem consumir nenhum símbolo de entrada (transições epsilon).

Question 32

O que é uma cadeia vazia e como é representada?

Answer 32

Uma cadeia vazia é uma sequência de símbolos que não contém nenhum símbolo. É representada pelo símbolo ε.