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.
Notação de de um conjunto definido por compreensão
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.
Exemplo linguagens de A={0,1}
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.
