Anotações Informática Teórica

Inform´atica Te´orica
Rafael Farias Marinheiro
2012-2

Sum´ ario I
II

Introdu¸c˜ ao 2

Alfabetos, Cadeias e Linguagens

4

1 Introdu¸ c˜ ao
1.1 Opera¸c˜ oes com Linguagens . . . . . . . . . . . . . . . . . . . . .

5
5

2 Reconhecedores de Linguagens
2.1 Estimando o n´ umero de linguagens sobre um alfabeto finito . . .

8
8

3 Reconhecedores de Linguagens Simples
3.1 Automatos finitos e aceita¸c˜ao . . . . . .
3.2 Linguagem de um Autˆomato Finito . . .
3.3 Opera¸c˜ oes Regulares . . . . . . . . . . .
3.3.1 Propriedades de Fechamento . .

1

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

10
10
11
13
13

Parte I

Introdu¸ c˜ ao

2

A teoria da computa¸c˜ ao ´e o ramo da matem´atica que estuda os modelos matem´ atica do fenˆ omeno da computa¸c˜ao. Iso t´e, define e analiza o conceito de algoritmo, assim como as no¸c˜oes de linguagem simb´ olica e m´ aquina de processar/reconhecer linguages.

3

Parte II

Alfabetos, Cadeias e
Linguagens

4

Cap´ıtulo 1

Introdu¸ c˜ ao
Defini¸
c˜ ao 1.1 (Alfabeto). Um alfabeto ´e um conjunto de s´ımbolos
Defini¸
c˜ ao 1.2 (Cadeia). Suponha que Σ seja um alfabeto finito. Uma cadeia sobre Σ ´e uma sequˆencia de s´ımbolos de Σ. Define-se tamb´em Σ∗ como sendo o conjunto de todas as palavras finitas sobre Σ.
Defini¸
c˜ ao 1.3 (Tamanho de uma cadeia). Seja Σ um alfabeto e w uma cadeia sobre Σ. O comprimento de w, denotado de |w| ´e definido como sendo o n´ umero de s´ımbolos de w. A cadeia de comprimento 0 ´e chamada de cadeia vazie e ´e normalmente denotade por
Defini¸
c˜ ao 1.4 (Reversa de uma cadeia). Seja Σ um alfabeto e w uma cadeia sobre Σ. A reversa de uma cadeia denotada por wR ´e basicamente ela lida ao contr´ ario 1
Defini¸
c˜ ao 1.5 (Concatena¸ca˜o de cadeias). Seja Σ um