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.

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.