Universidade Católica de Pelotas
Escola de Informática
Bacharelado em Ciência da Computação
Bacharelado em Sistemas de Informação
Alfabetos, Palavras e Linguagens
Prof. Luiz A M Palazzo
Pelotas, fevereiro de 2011
Alfabeto
•
É um conjunto finito de símbolos.
•
Pode ser vazio.
•
Símbolo: Entidade básica sem definição formal.
•
Exemplos: Letras, dígitos, ícones, etc.
Linguagens Formais e Autômatos - 03
2
Palavra, Cadeia ou Sentença
•
É uma seqüência finita de símbolos (do alfabeto) justapostos.
•
Palavra vazia: 
•
Alfabeto: 
•
Conjunto de todas as palavras possíveis sobre : *
•
+
•
Exemplos de palavras sobre  = {a, b}: , a, b, aa, ab, ba, bb, ...
=
* - {}
@
Linguagens Formais e Autômatos - 03
%
&
3
Tamanho de uma Palavra
• É o número de símbolos
existentes na palavra.
• Se w é uma palavra, o
tamanho de w é
representado por |w|.
• Por exemplo: Se w =
aaba, então |w| = 4.
• || = 0.
Linguagens Formais e Autômatos - 03
aaba
4
Prefixo, Sufixo e Subpalavra
• Prefixo de uma palavra é
qualquer seqüência inicial de
símbolos da palavra.
• Sufixo de uma palavra é
qualquer seqüência final de
símbolos da palavra.
• Subpalavra é qualquer
seqüência contígua de
símbolos da palavra.
• Exemplo: Identificar os
prefixos, sufixos e
subpalavras de “aaba”.
Linguagens Formais e Autômatos - 03
aaba:
, a, aa, aab, aaba
, a, ba, aba, aaba
, a, b, aa, ab, ba, aab, aba, aaba
5
Linguagem Formal
• É um conjunto de palavras sobre um alfabeto.
• Exemplos: {}, {}, {a, b, aa, ab, ba, bb, aaa, ...}.
• Aplicações: Modelos dinâmicos, processos de automação,
provadores de teoremas, interpretadores, compiladores, lógica
temporal, automação, robótica, prototipação, etc.
Linguagens Formais e Autômatos - 03
6
Concatenação de Palavras
• Operação binária, sem
representação.
• É a justaposição de duas ou mais
palavras, produzindo uma terceira
que é formada pelos símbolos da
primeira, na ordem em que
ocorrem, seguidos pelos símbolos
da segunda, também na ordem em
que ocorrem e assim
sucessivamente.
a a
b a
----------------a a b a
• Exemplo: Se v=aa e w=ba então
x=vw=aaba e y=wv=baaa.
Linguagens Formais e Autômatos - 03
7
Propriedades da
Concatenação
• Associatividade: v(wt) = (vw)t.
• Elemento Neutro: w = w = w.
v=aa, w=b, t=a  v(wt) = (vw)t = aaba
u=aaba  u = aaba = u
Linguagens Formais e Autômatos - 03
8
Concatenação Sucessiva
• De uma palavra repetidas
vezes com ela mesma.
• Notação: wn, onde n  0 é o
número de vezes que a
palavra é repetida.
(ab)3 = ababab
• w3 = www.
• w1 = w.
• w0 = , para w  .
Linguagens Formais e Autômatos - 03
9