Esta aula se baseia no livro de Peter Linz - Introdution to Formal Languages and Automata

Conceitos Basicos

  • simbolos: sao utilizados na composicao de palavras/cadeias.

  • alfabetos: um conjunto finito de simbolos. -> podemos denotar um alfabeto pelo simbolo grego $\Sigma$

  • cadeias/strings: uma sequencia de tamanho determinada de simbolos justapostos. -> podemos denotar uma cadeia por um simbolo contido no final do alfabeto greco-romano, como x, w, ou z, por exemplo.

  • linguagens: um conjunto definido sobre um alfabeto, o qual contem diversas combinacoes de simbolos do alfabeto. -> podemos denotar uma linguagem por $L = \lbrace \rbrace$

  • concatenacao: podemos concatenar 2 strings, e o resultado obtido eh o simples acrescimo de uma cadeia na direita da outra. ex: $w = a_1 a_2 \dots a_n$ e $v = b_1 b_2 \dots b_m$. Portanto, sua concatenacao sera $wv = a_1 a_2 \dots a_n b_1 b_2 \dots b_m$

  • reversao: reverter uma string eh apenas troca a ordem do indice i. Ao inves de comecar a escrever por i = 0, comecamos por i = n. -> Ex: $w^{R} = a_{n} \dots a_2 a_1$

  • tamanho: o tamanho de uma cadeia eh a quantidade de simbolos nela.

cadeia vazia: $| \lambda | = 0$

  • sub cadeia: sub conjunto de uma cadeia contido em uma cadeia. Tambem pode ser um prefixo ou sufixo.

Um alfabeto pode ser descrito sem a cadeia vazia: $$\Sigma^+ = \Sigma^* - {\lambda}$$

Uma cadeia que esta contida em uma linguagem L sera chamada de Sentenca.