Conceito básicos e terminologia
Um conjunto pode ser definido por:
extensão (ou enumeração),
Ex: conjunto dos algarismos básicos {0,1},
compreensão,
notação { x | p(x)} ou { x : p(x)}, x é a variável que representa qualquer elemento do conjunto, p(x) é o predicado sobre esta.
Um símbolo é uma unidade atómica, e um alfabeto é um conjunto finito de símbolos.
A = {0,1} é o alfabeto dos algarismos binários.
A = {0, 1,...,9} é o alfabeto de algarismos decimais.
String
É uma sequência de símbolos de um dado alfabeto.
Palavra vazia
É uma sequência de zero símbolos e denota-se por (épsilon). Sendo que épsilon não pertence ao alfabeto.
Sub-palavra
De uma palavra u, é uma sequência contígua de 0 ou mais símbolos de u.
Prefixo
É uma sequência contígua de 0 ou mais símbolos iniciais de u.
Sufixo
É uma sequência contígua de 0 ou mais símbolos terminais de u.
Fecho
Do alfabeto A é designado por A*.
Representa o conjunto de todas as palavras definíveis sobre o alfabeto A, incluindo a palavra vazia.
{0;1}* = { epsilon;0;1;00;01;10;11;000;001;...}
Linguagem
(Do alfabeto A) É um conjunto finito ou infinito de palavras válidas definidas com símbolo de A.
Uma vez que as linguagens são conjuntos, todas as operações matemáticas sobre conjuntos são aplicáveis: reunião, intercepção, complemento, diferença, etc.
Last updated
