Empty

Disponível somente no TrabalhosFeitos
  • Páginas : 11 (2584 palavras )
  • Download(s) : 0
  • Publicado : 14 de abril de 2013
Ler documento completo
Amostra do texto
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çasobre 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ãoxy = corredor.

Para duas palavras x e y, temos que |xy| = |x| + |y|.
A palavra vazia e é o elemento neutro da operação de
concatenação: ex = xe = x.

Definições
Notação 5: Para um símbolo s  S, denotamos sk a
palavra:

sk = ss...s
k

Notação 6: Da mesma forma se x é uma palavra,
denotamos a concatenação de k cópias de x por xk.

Definições
Notação 7: Uma linguagem é umconjunto de palavras
sobre um determinado alfabeto. Ou seja, se L é uma
linguagem, então L  S*.
Exemplos:
Seja S = {a,b,c,...,z}, L = conjunto de palavras da língua
inglesa.
Seja S = {0,1} e P = conjunto das palavras com n bits 0 seguidos de n
bits 1, para n ≥ 0.
P = {e,01,0011,...} = {0n1n : n > 0}.

Definições
Observações:
Seja S um alfabeto qualquer, então S*, ∅ e {e} são semprelinguagens sobre S.
Note que ∅ e {e} não são a mesma linguagem.
Alfabetos são sempre finitos e não-vazios, mas linguagens
podem ser conjuntos infinitos ou vazios.

Definições
Definição 7: Dadas as linguagens A e B, a concatenação
AB é uma linguagem definida de seguinte forma:
AB = {xy: x  A, y  B}
Considere as linguagens A = {falar,ver} e B = {ei,ás,á,emos,eis,ão},
temos que AB = {falarei,falarás, falará, falaremos, falareis, falarão,
verei, verás, verá, veremos, vereis, verão}.
Notação 8: A concatenação de L com ela mesma k vezes é denotada
como Lk = LL...L.

k

AUTÔMATOS FINITOS:
Definição Formal

Definição Formal de um Autômato Finito
Para definirmos um Autômato Finito, precisamos definir:
 O conjunto de estados.
 As funções de transição de estados.
 Umalfabeto que indica os símbolos de entrada
permitidos.

 O estado inicial.
 Os estados de aceite.

Definição Formal de um Autômato Finito
A definição formal de um Autômato Finito é então uma lista
com esses cinco elementos.
Na matemática, tal estrutura é denominada 5-tupla
(quíntupla). Então temos:
M = (Q, S, d, q0, F)

Definição Formal de um Autômato Finito
M = (Q, S, d, q0, F)...
tracking img