Terminologia

Conjuntos são representados por seqüências de elementos entre chaves, como em

$$\{1,2,3\}$$

Nomes de conjuntos serão usualmente representados por letras maiúsculas,

$$A = \{1,2,3\}$$

Operações entre conjuntos incluem união ($\cup$), interseção ($\cap$) e diferença ($-$),

$$\{1,2\} \cup \{2,3\} = \{1,2,3\}$$

$$\{1,2\} \cap \{2,3\} = \{2\}$$

$$\{1,2\} - \{2,3\} = \{1\}$$

Os relacionamentos de inclusão entre conjuntos são inclui ( $\supset, \supseteq$) e é incluído ( $\subset, \subseteq$),

$$\{1,2,3\} \supset \{1\}$$

$$\{1,2,3\} \supseteq \{1\}$$

$$\{1,2,3\} \subseteq \{1,2,3\}$$

$$\{1,2\} \subset \{1,2,3\}$$

O símbolo $\in$ é usado para expressar o relacionamento de pertinência de elemento em conjunto,

$$1 \in \{1, 2, 3\}$$

O conjunto vazio é denotado pelo símbolo $\emptyset$, como em

$$\{1, 2\} \cap \{3, 4\} = \emptyset$$

Um conjunto pode também ser definido por um predicado, como

$$A = \{ x \mid x \in \mathbb{N}$$    e $$x < 4\}$$

Um alfabeto (ou um vocabulário) é um conjunto de símbolos. Se $A$ é um alfabeto, então a clausura de $A$, denotada $A^\ast$, é o conjunto de todas as strings -- incluindo a string vazia, denotada $\varepsilon$ -- compostas a partir de símbolos de $A$. Por exemplo, para $A = \{0,1\}$

$$A^\ast = \{ \varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, \dots \}$$

$A^+$ é o conjunto de todas strings compostas a partir de $A$ sem incluir a string vazia, ou seja,

$$A^+ = A^\ast - \varepsilon$$

Uma linguagem é uma especificação de quais strings, dentre todas possíveis associadas a um conjunto de símbolos, são válidas (aceitáveis) para uma aplicação.

Linguagens simples podem ser definidas diretamente em termos de notação de conjuntos. Por exemplo, a linguagem

$$L = \{ 0^n1^n \mid n \geq 0 \}$$

denota que sentenças válidas na linguagem $L$ estão no conjunto de todas as strings compostas de 0's e 1's iniciadas por $n$ 0's seguidos por igual número de 1's. Observe que a string vazia está incluída nesta linguagem, ou seja, é uma sentença válida em $L$, uma vez que $n$ pode ser 0.

Linguagens mais complexas, como aquelas envolvidas na programação de computadores, dificilmente podem ser representadas de forma tão simples como esta. Para tanto, é preciso especificar a linguagem através de uma gramática. Uma das partes de uma gramática é o conjunto de regras que indica como gerar sentenças em uma linguagem. Por exemplo, para a mesma linguagem $L$ as seguintes regras podem ser utilizadas:

$$S \rightarrow 0 S 1$$

$$S \rightarrow \varepsilon$$

A interpretação destas regras é a seguinte. Para gerar uma sentença nesta linguagem, comece com o símbolo $S$ e substitua-o por $0S1$ ou por $\varepsilon$. Cada vez que o símbolo $S$ estiver presente na sentença gerada, ele pode ser novamente substituído por uma das duas opções. Qualquer string produzida dessa forma e que não contenha $S$ será uma sentença da linguagem.

O processo de substituir o símbolo $S$ pelo lado direito de uma regra é denominado uma derivação. Por exemplo, a sentença 0011 pode ser construída pela seqüência de derivações

$$S \Longrightarrow 0S1 \Longrightarrow 00S11 \Longrightarrow 0011$$

Todas as sentenças em $L$ podem ser geradas a partir dessas duas regras. Qualquer string que não possa ser gerada a partir delas não será uma sentença em $L$.