Linguagem - Teoria da Computação

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
 
MAJS - FTC
Linguagem
Conjunto de strings/sentenças.
String/sentença: uma seqüência finita de elementos construída a partir de uma base.
Alfabeto (S):
conjunto de símbolos que permitem derivar os strings da linguagem.
Convenções
letras a, b, c... são usadas para representar os elementos de um alfabeto.
p, q, u, v, w, x, y, z são usadas para representar strings gerados a partir de um alfabeto.
*
 
MAJS - FTC
Fecho - Estrela de Kleene
Considere S um alfabeto. S* representa o conjunto de todos
os strings gerados por S.
Formalmente:
base: l Î S*.
passo recursivo: se w Î S* e a Î S então wa Î S*.
fechamento: w Î S* somente se puder ser obtido a partir de l com um nº finito de aplicações do passo recursivo.
 
*
 
MAJS - FTC
Exemplo
Se S = { a } então: S* = { l , a, aa, aaa, ... }.
Se S = { while, >, id } então: 
S* = { l, while, while > id >, while id > id, ... }.
Nota:
se S ¹ Æ , então S* contém infinitos elementos.
se S = Æ , então S* contém apenas { l }.
*
 
MAJS - FTC
Propriedades e Operações com strings
O tamanho/comprimento de um string w - length(w):
nº de aplicações do passo recursivo para se obter w.
Exemplo: se S = {a, b, c}, os elementos de S* incluem:
		tamanho 0: l 
		tamanho 1: a b c 
		tamanho 2: aa ab ac ba bb bc ca cb cc
*
 
MAJS - FTC
Propriedades e Operações com strings
Seja u, v Î S*. A concatenação de u e v, escrita uv, é uma operação binária em S*:
base: se length(v) = 0, então v = l e uv = u.
passo recursivo: se length(v) = n > 0, então v = wa e uv = (uw)a
 (length(w) = n – 1, a Î S).
	 			 	 
*
 
MAJS - FTC
Propriedades e Operações com strings
Exemplo:	u = ab, v = ca, w = bb
			uv = abca vw = cabb (uv)w 	= abcabb u (vw) = abcabb 
Concatenação é associativa? (uv)w = u(vw).
*
 
MAJS - FTC
Teorema
Considere u, v, w Î S*: (uv)w = u(vw).
Prova: por indução no comprimento do string w.
base: length(w) = 0, então w = l e (uv)w = (uv)l = uv. 
 Analogamente, u(vw) = u(vl) = u(v) = uv.
hipótese: assuma que (uv)w = u(vw)  w, length(w) £ n.
passo indutivo: provar que (uv)w = u(vw) Ö w, length(w) = n + 1. 
*
 
MAJS - FTC
Considere w tal string: 
w = xa, length(x) = n, a Î S.
	(uv)w = (uv)xa
	 	 = ((uv)x)a	“definição de concatenação”
	 = (u(vx))a 	“hipótese”
	 = u((vx)a) 	“definição de concatenação”
	 = u(v(xa))	“definição de concatenação”
	 = u(vw) C.Q.D. 
*
 
MAJS - FTC
Notas
Concatenação não é comutativa.
x é um substring de y se $ x , v, z I y = zxv.
x é dito prefixo de y se z = l, ou seja, y = xv.
x é dito sufixo de y se v = l, ou seja, y = zx.
*
 
MAJS - FTC
Definição
Considere w  S*. O reverso de w, denotado wR, é definido por:
base: length(w) = 0. Então w = l e lR = l. 
passo recursivo: se length(w) = n ³ 1, então w = ua e wR = auR para length(u) = n - 1, a Î S. 
*
 
MAJS - FTC
Teorema
Considere x, y Î S*: (xy)R = yR xR. 
Prova por indução no comprimento de y.
base:	se length(y) = 0, então y = l e (xy)R = (xl)R = xR.
	 		Analogamente yR xR = lR xR = xR.
hipótese: assuma que (xy)R = yRxR Ö length(y) £ n.
passo indutivo: provar que (xy)R = yR xR para length(y) = n+1.
*
 
MAJS - FTC
Considere y tal string:
y = wa, length(w) = n, a Î S.
	(xy)R = (x (wa))R
	 = ((xw) a)R		associatividade
	 = a(xw)R 	definição de reverso
	 = a(wRxR) 		hipótese
	 = (awR)xR 	associatividade
	 = (wa)RxR 	 	definição de reverso
	 = yRxR 	C.Q.D. 
*
 
MAJS - FTC
Linguagem
Na realidade, certas restrições são impostas aos strings:
propriedades - sintaxe da linguagem.
Nova definição:
Uma linguagem L é um subconjunto de S* (L  S*). 
*
 
MAJS - FTC
Operações
A concatenação da linguagem X e Y, denotada XY, é a linguagem 
	XY = {xy I x Î X e y Î Y}
Exemplo:
		X = {a, b, c} Y = {abb, ba}
		XY = {aabb, aba, babb, bba, cabb, cba}
		X0 = { l }
	 	X1 = {a, b, c}
		X2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc}	
*
 
MAJS - FTC
Operações
Considere X  S*:
 X* = 	X+ =
		 Fecho			Fecho positivo
*
 
MAJS - FTC
Especificação de Linguagem
Requer uma descrição não ambígua dos strings
Seja S = { a, b } e L  S* a linguagem de todos os strings que contém bb.
Ambigüidades:
uma só ocorrência de bb?
várias ocorrências de bb?
no mínimo uma ocorrência de bb ?
*
 
MAJS - FTC
Especificando Linguagens
Considere S = { a, b }.
L = {a, b}* {bb} {a,b}* 
A linguagem contêm pelo menos uma ocorrência de bb.
L = {aa} {a, b}* È {a, b}* {bb}
A linguagem que possui prefixo aa ou sufixo bb.
*
 
MAJS - FTC
Especificando Linguagens
Considere S = { b } e L1 = {bb}, L2 = {l, bb, bbbb}.
 L1* e L2* - precisamente a linguagem de todos os strings consistindo de um número par de b’s.
	L1* = {l, bb, bbbb, bbbbbb, ... } 
	L2* = {l, bb, bbbb, bbbbbb, ... }
*
 
MAJS - FTC
Um conjunto é dito regular se pode ser gerado, a partir de S, usando apenas as operações de fecho, união e concatenação.
Definição recursiva:
base: Æ, { l } e { a } Ö a Î S , são conjuntos regulares.
passo recursivo: se X, Y são conjuntos regulares, então XÈY, XY, X* são regulares.
Conjuntos Regulares
*
 
MAJS - FTC
O conjunto cujos strings começam e terminam em a e contêm pelo menos um b.
{a} {a, b}* {b} {a, b}* {a}
Observação:
fecho tem a mais alta prioridade seguida da concatenação e união.
Exemplo
*
 
MAJS - FTC
Abreviação para conjuntos regulares.
Definição recursiva:
base: Æ, l e a Ö a Î S, são expressões regulares em S.
passo recursivo: se u e v são expressões regulares, então
	 uÈv, uv e u* são expressões regulares.
Expressão Regular
*
 
MAJS - FTC
{a} {a, b}* {b} {a, b}* {a} = a (a È b)* b (a È b)* a
{a, b}* {bb} {a, b}* = (a È b)* bb (a È b)*
Nota:
(a I b)* bb (a I b)* = (a È b)* bb (a È b)*
x+ denota xx*
x2 denota xx, x3 denota x2x ...
Mostre que { bawab I w Î {a, b}* } é regular em S = {a, b}. Exibir a cada passo a expressão regular correspondente.
Exemplo
*
 
MAJS - FTC
Identidades
		1) Æ w = w Æ = Æ 2) l w = w l = w 
		3) Æ* = l	 4) l* = l
		5) w È y = y È w 6) w È Æ = w
		7) w È w = w 8) w*w* = w*
		9) (w*)* = w* 10) w*w = ww* = w+ 
*
 
MAJS - FTC
Identidades
		11) w (x È y) = wx È wy
		12) (x È y) w = xw È yw
		13) (wy)* w = w (yw)*
		14) (w È y)* 	= (w* È y)*
				= w* (w È y)*
 				= (w È yw*)*
 				= (w* y*)*
				= w* (yw*)*
				= (w*y)* w*
*
 
MAJS - FTC
Aplicação
Mostre que:
a* (a* ba* ba* )* = a* (ba* ba*)*.
b* (ab+)* È b* (ab+)* a = (b È ab)* (l È a).
Verifique se acabacc e bbaaacc estão no conjunto representado por c* (b È (ac*))*. 
Nota:
É importante observar que existem linguagens que não podem definidas por expressões regulares: { anbn I n ³ 0 }.