informatica

Matemática Computacional -Jairo Viana Júnior

Uma linguagem formal, ao contrário de uma linguagem natural, é tal que:
◦ tem uma sintaxe bem definida, de tal forma que, dada uma sentença, é sempre possível saber se ela pertence ou não á linguagem;
◦ tem uma semântica precisa, de tal forma que não contém sentenças sem significado ou ambíguas.



Alfabeto é um conjunto finito de símbolos
(entidade abstrata básica sem definição).
◦ Σ* = Todas as palavras possíveis sobre Σ
◦ Σ+ = Todas as palavras possíveis sobre Σ menos λ
(Σ+ = Σ* - λ)



Palavra sobre um alfabeto é uma sequência finita de símbolos pertencentes ao alfabeto.
◦ Se X é uma palavra , |X| é o número de símbolos que a compõem.
◦ λ ou ε é a palavra vazia, ou seja, a palavra com 0 símbolos. 






Σ* = {λ, 1, 11, 111, 1111,...}
10 = λ
14 = 1111
É possível representar qualquer número em ℕ
Um número natural N gastaria N símbolos para a representação Alfabeto Σ={1}








Γ * = {λ, 0,1, 00, 01, 10, 11,
000, 001, 010,...}
10 02 = λ 00 = 00
04 1 02 = 0000100
É possível representar qualquer número natural?
Um número natural N gastaria log2n - 1 símbolos para a representação

Alfabeto Γ={0,1}

Uma linguagem sobre um alfabeto Σ é um conjunto de palavras sobre Σ. Denotando o conjunto de todas as palavras sobre Σ por Σ∗ , diz-se, então, que uma linguagem sobre Σ é qualquer subconjunto de Σ ∗. Ou ainda:

L é uma linguagem sobre Σ se, e somente se, L ⊂ Σ*



Se L 1 e L 2 são linguagens sobre os alfabetos Σ1 e Σ2 respectivamente, podemos dizer que:
◦ L 1 ∪ L 2, uma linguagem sobre Σ1 ∪ Σ2
◦ L 1 ∩ L 2, uma linguagem sobre Σ1 ∩ Σ2
◦ L 1 - L 2, uma linguagem sobre Σ1
É possível que L 1 esteja contida em L 2?



Concatenação (palavra xyz)
◦
◦
◦
◦
◦

Prefixo (x)
Sufixo (z)
Subpalavra (y)
Reverso (xyz)R λ é prefixo, sufixo e subpalavra de toda palavra



Concatenações
◦ λ(ab) = (ab)λ = ab
◦ (abc)(aabb) =