next up previous contents
Next: Definição formal Up: Gramáticas Previous: Gramáticas   Sumário

Terminologia

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

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

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

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

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

$\displaystyle \{1,2\} \cup \{2,3\}$ $\displaystyle = \{1,2,3\}$    
$\displaystyle \{1,2\} \cap \{2,3\}$ $\displaystyle = \{2\}$    
$\displaystyle \{1,2\} - \{2,3\}$ $\displaystyle = \{1\}$    

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

$\displaystyle \{1,2,3\} $ $\displaystyle \supset \{1\}$    
$\displaystyle \{1,2,3\} $ $\displaystyle \supseteq \{1\}$    
$\displaystyle \{1,2,3\} $ $\displaystyle \subseteq \{1,2,3\}$    
$\displaystyle \{1,2\}$ $\displaystyle \subset \{1,2,3\}$    

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

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

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

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

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

$\displaystyle A = \{ x \mid x \in \mathbb{N}$    e $\displaystyle 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\}$

$\displaystyle 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,

$\displaystyle 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

$\displaystyle 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:

$\displaystyle S$ $\displaystyle \rightarrow 0 S 1$    
$\displaystyle S$ $\displaystyle \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

$\displaystyle 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$.


next up previous contents
Next: Definição formal Up: Gramáticas Previous: Gramáticas   Sumário
Ivan L. M. Ricarte 2003-02-14