itc - itc Flashcards
O que é um alfabeto em teoria da computação?
Um conjunto finito e não vazio de símbolos.
O que é uma cadeia?
Uma sequência de símbolos de um alfabeto.
Como se denota a cadeia vazia?
Por ε ou λ.
O que é o comprimento de uma cadeia?
O número de símbolos que a cadeia contém.
O que é o reverso de uma cadeia?
A cadeia escrita na ordem inversa.
O que é uma subcadeia?
Uma sequência de símbolos que aparece dentro de outra cadeia.
O que é concatenação de cadeias?
A união de duas cadeias, colocando uma após a outra.
O que é a potência de uma cadeia?
A concatenação da mesma cadeia várias vezes.
O que é o Fecho de Kleene (Σ*)?
O conjunto de todas as cadeias possíveis sobre o alfabeto Σ.
O que é uma linguagem em teoria da computação?
Um conjunto de cadeias (finito ou infinito) que é um subconjunto de Σ*.
Quais são os componentes de um autômato finito?
Estados, alfabeto de entrada, função de transição, estado inicial, e conjunto de estados de aceitação.
O que são estados de aceitação em um autômato finito?
Estados nos quais, se o autômato termina o processamento da cadeia de entrada, a cadeia é aceita.
O que é a função de transição em um autômato finito?
Uma função que define para cada par (estado atual, símbolo de entrada) o próximo estado.
O que é a linguagem reconhecida por um autômato finito?
O conjunto de cadeias que o autômato aceita.
Qual é a diferença entre um autômato finito determinístico (DFA) e um não determinístico (NFA)?
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.
Dê um exemplo de aplicação prática de um autômato finito.
Um controlador de portas que muda de estado (aberto/fechado) com base em sinais de entrada (frente/atrás/ambos/nenhum).
O que cada símbolo da 5-tupla (Q, Σ, δ, q0, F) representa?
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.
O que é um autômato finito?
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.
Qual é a definição formal de um autômato finito?
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.
O que é a operação módulo em matemática?
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.
Como um autômato finito processa uma cadeia de entrada?
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
O que significa dizer que uma linguagem é regular?
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.
Quais são as operações regulares que podem ser aplicadas às linguagens regulares?
As operações regulares incluem união, concatenação e estrela (fechamento de Kleene).
O que significa a operação de união de linguagens regulares?
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).
O que significa a operação de concatenação de linguagens regulares?
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.
O que é a operação estrela (fechamento de Kleene) de uma linguagem regular?
A operação estrela, denotada por A*, resulta em uma nova linguagem formada por zero ou mais concatenações de cadeias de A.
O que significa dizer que a classe das linguagens regulares é fechada sob uma operação?
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.
Qual a importância das definições formais na teoria da computação?
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.
Qual é a função de transição em um autômato finito?
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.
O que significa que um autômato é determinístico?
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.
O que é um autômato não-determinístico?
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).
O que é uma cadeia vazia e como é representada?
Uma cadeia vazia é uma sequência de símbolos que não contém nenhum símbolo. É representada pelo símbolo ε.
