Introdução a linguagens formais

CICLO DE VIDA DE UM CÓDIGO-FONTE

ALFABETO - É um conjunto finito (não vazio) de símbolos. Exemplo: {a, b, c}.
Notação: Σ ou T

SÍMBOLO - É um elemento de um alfabeto. “a”, “b”, “c”. Exemplos:

SÍMBOLO
CONJUNTO DE CADEIAS

Σ0 = {0,1}
0
011
0011

SÍMBOLO
CONJUNTO DE CADEIAS

Σ1= {a,b, c, ..., z} casa aab cc CADEIA ou PALAVRA - Sequência de símbolos. Exemplo: ab, abb, aabb.
Notação para indicar cadeia vazia: ƛ ou Ɛ.
Notação para indicar o tamanho de uma cadeia: | α |
LINGUAGEM
É gerado a partir de um conjunto de cadeias.

OPERAÇÕES E RELAÇÕES
Reverso ou inverso: indica o contrário da cadeia - de trás para frente. É denotada por ΣR. Exemplo: Σ1= {a,b, c, ..., z}, logo o reverso é ΣR = {z, ..., c, b, a}.
O reverso de uma cadeia vazia é a própria cadeia vazia: ƛR = ƛ;
Reverso de duas cadeias: (VW)R = WR VR.
Propriedade da concatenação
Associatividade: (UV)W = V(VW)
Elemento neutro: U ƛ = ƛV = V
|UV| = |U| + |V| σi onde σ é concatenado i vezes
ƛ0 = ƛ x¹ = x x² = xx x³ = xxx
Subcadeia ou subpalavra: é qualquer subcadeia formada por um símbolo contíguos (adjacentes) de uma cadeia.
Prefixo e sufixo. Exemplo: Flamengo
Prefixo: Fla
Sufixo: Mengo
Interseção e união: tendo duas cadeias: Σ1= {aa, b} e Σ2= {aa, bb, ba}
Interseção de Σ1 ∩ Σ2 = {aa}
União de Σ1 U Σ2 = {aa, b bb, ba}
Complemento: é tudo aquilo que tem em um conjunto, mas não tem em outro. Denotado por: ¬Σ = Σ2 - Σ1. Logo, significa: tudo que tem em Σ2 e não tem em Σ1.

RESUMO DA AULA

Um alfabeto - denotado por Σ ou T - contém um conjunto de símbolos, onde este, é uma sequência de cadeias ou palavras que formam uma linguagem. A denotação para cadeia vazia é dada por ƛ ou Ɛ, e a denotação para obter o tamanho da cadeia é dado por | α |. Existem as operações e relações que são usadas na linguagem, são elas:
Reverso, que indica o contrário de uma cadeia, ou seja, o inverso. Caso exista uma cadeia vazia, o reverso da mesma é a própria cadeia;