Linguagem - created from Mind Map

Página 1

Conjunto de Palavras sobre um alfabeto

cadeia

Sequência finita de simbolos de um alfabeto

JAVA

Finita

Para uma linguagem finita, para usa representação, basta listar todas as cadeias

Infinita

Para linguagens infinitas, existem 2 sistema principais para representação

Palavra

Cadeia Vazia

Elemento neutro de uma operação de contcatenação

Cadeia não vazia

Seja o alfabeto {a, b, c}, são palavras ou cadeias { caba, caca, ca, .... }

Operações (concatenação)

Fechamento Positivo (sigma +)

Conjunto de todas as cadeias possiveis de um alfabeto menos a cadeia vazia

Fechamento de Kleene (sigma *)

Conjunto de todas as cadeias possiveis de um alfabeto + a cadeia vazia

{0, 1}³ = { 000, 001, 010 ... }

{a, b}* = { cadeia vazia, a, b, aa, bb, ab...}

Gramatica

Sistema gerador

Automato

Sistema reconhecedor que opera de maneira automatica apenas cumprindo um conjunto de ordens.

4-upla

Formas setenciais são a própria árvore de derivação associada à gramatica, enquanto a linguagem gerada contitui o conjunto das folhas das árvores

Conjunto de terminais

Conjunto de não terminais

Simbolo não terminal Inicial

Regras de Produção

{ a, b }

{ A, S}

S

P = { S -> a }

P = {

S -> ab ,

S -> aASb ,

S -> bSb ,

AS -> bSb

}

Finito

Conjunto de estados, alguns dos quais são denominados estados finais. à media que caracteres de entrada são lidos, o controle da máquina passa de um estado a a outra através de um conjunto de regras de transição especificadas para o autômato.

Deterministico (AFD)

Para um automato ser deterministico ele deve cobrir todas as possibilidades. Exite informação suficiente para sempre determinar qual é o proximo estado para qual o automato vai, ao ler um dado simbolo

Linguagem regular

Programa que compila

Alfabetos

Conjunto não vazio de simbolos

Class, For, Whie...