Empty

LINGUAGENS FORMAIS
E AUTÔMATOS
Prof. Fabrício Olivetti de França

DEFINIÇÕES

Definições
Definição 1: Um alfabeto é um conjunto finito não-vazio.

Definição 2: Os elementos de um alfabeto são chamados símbolos. Definição 3: Uma sentença ou palavra é uma sequência finita de símbolos. Se todos os símbolos de uma sentença w pertencem a um alfabeto S, dizemos que w é uma sentença sobre S.

Definições
Considere S = {0,1}. Então 0 e 1 são símbolos de S. As sequências 0010, 11011101, 111011000 são exemplos de sentenças sobre S.
Considere S = {a,b,c,..,z}. Então as sequências abacaxi, doce, quadrado e mxyzptlk são exemplos de sentenças sobre S.

Definições
Notação 1: Dada uma sentença w e um símbolo s, denotamos por nw(s) o número de ocorrências de s em w.
Se w = aababababbb, então nw(a) = 5 e nw(b) = 6. Para esse caso, nw(x) = 0.
Definição 4: A palavra vazia é uma palavra e é denotada pela letra grega e.

Definições

Definição 5: O comprimento de uma palavra é o número de símbolos nela contido. Denotamos por |w|.
A palavra ababba tem comprimento 6, ou seja, |ababba| =
6. O comprimento de uma palavra vazia é 0, |e| = 0.

Definições
Notação 2: Uma palavra de comprimento 3 sobre S é uma sequência de tamanho 3 de símbolos de S e, portanto, é um elemento do conjunto S x S x S = S3. Denotamos então
Sk, para k ≥ 0, o conjunto de todas as palavras de comprimento k sobre S.

Sendo assim temos que: S0

= {e}, S1 = S.

Definições
Notação 3: O conjunto de todas as palavras sobre um alfabeto S é denominado por S*.

Σ ∗ = Σ 0 ⋃Σ 1 ⋃Σ 2 …

Definições
Notação 4: O conjunto de todas as palavras sobre um

alfabeto S, sem o alfabeto vazio, é denominado por S+.

+

1

2

Σ = Σ ⋃Σ … e Σ ∗ = Σ 0 ⋃Σ +

Definições
Definição 6: A concatenação das palavras x = s1s2...sn, com si  S e y = g1g2...gm, com gj  G, é a palavra: xy = s1s2...sn g1g2...gm sobre S U G.

Definições
Considere x = corre e y = dor, então