ATPS Teoria da Computação

e-Book: Linguagens Formais & Autômatos

http://teia.inf.ufrgs.br/library.html

Capítulo I

Introdução e Conceitos Básicos

Introdução

Teoria das Linguagens Formais foi originariamente desenvolvida na década de 1950 com o objetivo de desenvolver teorias relacionadas com as linguagens naturais. Entretanto, logo foi verificado que esta teoria era importante para o estudo de linguagens artificiais e, em especial, para as linguagens originárias na Ciência da Computação. Desde então, o estudo das Linguagens Formais desenvolveu-se significativamente e com diversos enfoques, com destaque para aplicações em Análise Léxica e Sintática de linguagens de programação, modelos de sistemas biológicos, desenhos de circuitos e relacionamentos com linguagens naturais. Recentemente, inclui-se a ênfase no tratamento de Linguagens Não-Lineares, como Planares, Espaciais e n-Dimensionais.

Conjuntos e Operações sobre Conjuntos

[pic 1]

Conjunto

Um Conjunto é uma coleção de zero ou mais objetos distintos, denominados Elementos do conjunto.

[pic 2]

Um elemento é uma entidade básica a qual não é definida formalmente. Relativamente ao relacionamento entre elementos e conjuntos, tem-se que:

a) Se um elemento a pertence a um conjunto A denota-se por a [pic 3]A; caso contrário, a [pic 4]A

b) Se todos os elementos de um conjunto A também são elementos de um conjunto B, então afirma-se que A está contido em B ou que A é subconjunto de B e denota-se por A B (ou ainda B contém A e B [pic 6]A). Adicionalmente, se existe b [pic 7]B tal que b [pic 8]A, então afirma-se que A está contido propriamente em B ou que A é subconjunto próprio de B e denota-se por A B (ou ainda B contém propriamente A e B A)[pic 5][pic 9][pic 10]

c) Os conjuntos A e B são iguais se, e somente se, possuem os mesmos elementos, ou seja, A = B se, e somente se, A B e B A[pic 11][pic 12]

[pic 13]

Um conjunto pode possuir um número finito ou infinito de elementos. Os conjuntos finitos podem ser denotados por extensão, listando todos os seus elementos entre chaves e em qualquer ordem como, por exemplo:

{ a, b, c }

O conjunto sem elementos (ou seja, com zero elementos) é denominado conjunto vazio e é denotado por {  } ou [pic 14]. Conjuntos (finitos ou infinitos) também podem ser denotados por compreensão na forma:

{ a [pic 15] a [pic 16]A e p(a) }     ou     { a [pic 17]A [pic 18] p(a) }

a qual é interpretada como:

"o conjuntos de todos os elementos a pertencentes ao conjunto A tal que p(a) é verdadeiro".

Quando é claro que a [pic 19]A, pode-se denotar simplesmente na forma: 

{ a [pic 20] p(a) }

[pic 21]

Conjuntos, Elementos

a) a [pic 22]{ b, a } e c [pic 23]{ b, a }

b) {a, b } = { b, a }, { a, b } { b, a } e { a, b } { a, b, c }[pic 24][pic 25]

c) Os seguintes conjuntos são infinitos:

Conjunto dos Números Naturais;[pic 26]

Conjunto dos Números Inteiros; [pic 27]

Conjunto dos Números Racionais; [pic 28]

[pic 29]Conjunto dos Números Irracionais;

[pic 30]Conjunto dos Números Reais.

d) { 1, 2, 3 } = { x [pic 31] [pic 33] x 0 e x [pic 35]4 } e = { x [pic 37] [pic 39] x [pic 40]0 }[pic 32][pic 34][pic 36][pic 38]

e) O conjunto dos números pares pode ser denotado por compreensão como segue:

{ y [pic 41] y = 2x e x [pic 42] }[pic 43]

[pic 44]

União, Intersecção, Diferença, Complemento, Conjunto das Partes, Produto Cartesiano

Sejam A e B conjuntos. Então: