Conjuntos são representados por seqüências de elementos entre chaves, como em
Nomes de conjuntos serão usualmente representados por letras maiúsculas,
Operações entre conjuntos incluem união (), interseção () e diferença (),
Os relacionamentos de inclusão entre conjuntos são inclui ( ) e é incluído ( ),
O símbolo é usado para expressar o relacionamento de pertinência de elemento em conjunto,
O conjunto vazio é denotado pelo símbolo , como em
Um conjunto pode também ser definido por um predicado, como
Um alfabeto (ou um vocabulário) é um conjunto de símbolos. Se é um alfabeto, então a clausura de , denotada , é o conjunto de todas as strings -- incluindo a string vazia, denotada -- compostas a partir de símbolos de . Por exemplo, para
é o conjunto de todas strings compostas a partir de sem incluir a string vazia, ou seja,
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
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 as seguintes regras podem ser utilizadas:
A interpretação destas regras é a seguinte. Para gerar uma sentença nesta linguagem, comece com o símbolo e substitua-o por ou por . Cada vez que o símbolo 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 será uma sentença da linguagem.
O processo de substituir o símbolo 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
Todas as sentenças em 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 .