SIA 262 idiomas

Introdução à Teoria da Computação

Jean GallierDepartment de Computador e Informações ScienceUniversity de PennsylvaniaPhiladelphia, PA 19104, USAe-mail:[email protected]

©c Jean GallierPlease, fazer notreproducewithout permissão do autor

Março 5, 2020

4 CONTEÚDO

• 6.4 O Bombeamento Lema
• 6.5 Um Algoritmo Rápido para Verificar o Estado de Equivalência
• 7 Gramáticas independentes de Contexto E Linguagens
• 7.1 Context-Free Grammars
• 7.2 Derivações e Livre de Contexto Idiomas
• 7.3 Formas Normais para Gramáticas independentes de Contexto
• 7.4 Regular de Idiomas são Livre de Contexto
• 7.5 Inútil Produções em Gramáticas independentes de Contexto
• 7.6 O Greibach Forma Normal
• 7.7 Menos Fixo de Pontos
• 7.8 Livre de Contexto Línguas Menos Fixo de Pontos
• 7.9 Menos Fixo e os Pontos de Greibach Forma Normal
• 7.10 Árvore de Domínios e Gorn Árvores
• 7.11 Derivações Árvores
• 7.12 Ogden Lema do
• 7.13 Pushdown Automata
• 7.14 De Gramáticas independentes de Contexto Para PDA
• 7.15 De PDA Para Gramáticas independentes de Contexto
• 7.16 O Chomsky-Schutzenberger Teorema
• 8 Uma Pesquisa ofLR-Análise de Métodos de
• 8.1 LR(0)-Característica de Autômato
• 8.2 Shift/Reduzir Analisadores
• 8.3 Cálculo da PRIMEIRA
• 8.4 A Intuição por Trás do Turno de trabalho e Reduzir o Algoritmo
• 8.5 O Gráfico Método para computar Pontos Fixos
• 8.6 Cálculo do SIGA
• 8.7 AlgorithmTraverse
• 8.8 outros Autômatos característicos do onLR
• 8.9 LALR (1) – Conjuntos de Lookahead
• 8.10 computando primeiro, seguir, etc. na Presença ofǫ-Regras
• 8.11 LR(1)-Característica de Autômato

Introdução

A teoria da computação preocupa com algoritmos e algoritmos de sistemas: theirdesign e representação, a sua integridade e a sua complexidade.

o propósito destas notas é introduzir algumas das noções básicas da teoria da computação, incluindo conceitos de linguagens formais e teoria de autômatos, a teoria da computabilidade, alguns conceitos básicos da teoria da função recursiva, e uma introdução à teoria da complexidadetheory. Outros tópicos como a correção de programas não serão tratados aqui (não há tempo suficiente!).

as notas estão divididas em três partes. A primeira parte é dedicada às línguas formais e aos autómatos. A segunda parte trata de modelos de computação, funções recursivas, eundecidabilidade. A terceira parte trata da complexidade computacional, em particular o classesPandNP.

5

Basics of Formal Language Theory

2.1 Review of Some Basic Math Notation and

n, Z, Q,R, C.

Thenatural numbers , N={ 0 , 1, 2,…}.

Theintegers, Z = {…,− 2 ,− 1 , 0 , 1 , 2 ,…}.

Therationals,

Q=

{

pq

|p,q∈Z, q 6 = 0

}

null

Thereals,R. Thecomplex números, C={a+ib|a,b∈R}.A notação f: X→Y

denota uma unidade comomainxandrange(orcodomain)Y.

graph(f) ={(x,f (x)}|x∈X}⊆X×Y

é o ponto final.

7

8 Capítulo 2. BASICS OF FORMAL LANGUAGE THEORY

Im (f) =f(X)={y∈Y |∃x∈X, y = f(x)}⊆Y

is theimageoff.

mais geralmente, ifA⊆X, então

f (A)={y∈Y | / x A A, y = f(x)}⊆Y

é a imagem(directa).

IfB⊆Y, then f− 1 (b) ={x∈X|f(x)∈B}⊆X

é a imagem Anversa(orpullback) de B.

f – 1 (b) é um conjunto; pode estar vazio mesmo ifB 6 =∅.Dadas duas functionsf:X→Y andg:Y→Z, a functiong◦f:X→Zgiven por

(g◦f)(x) =g(f(x)) para allx∈X

é thecompositionoffandg.

A função idX:X→Xgiven por

idX(x) =x para allx∈X

é theidentity função(ofX).

a functionf: X→Y isinjective (Old terminologyone-to-one)if for allx 1, x 2 ∈X,

iff (x 1 ) =f( x 2 ), thenx 1 =x 2 ;

equivalentemente ifx 16 = x 2, thenf(x 1 ) 6 =f (x 2 ).

fato: IfX 6 =∅(e soja 6 =∅), uma functionf:X →Y é injetivo iff há uma functionr:Y →X(inverso de aleft) tal que

r◦f= idX.

Nota: ris surjective.Um functionf:X→Y issurjective(antigo terminologyonto)se for aliado∈Y, existe somex∈Xsuch thaty=f(x), ifff(X) =Y.

Fato: IfX 6 =∅(e soja 6 =∅), um functionf:X→Y é surjective iff há uma funções:Y →X(amão inverseorsection) tais que a

f◦s= idY.

10 CHAPTER 2. FUNDAMENTOS DA LINGUAGEM FORMAL da TEORIA

UM relationR⊆X×Xissymmetricif para allx,y∈X, se (x,y)∈R, então (y,x)∈R

Um relationR⊆X×Xis simétrica iffR− 1 ⊆R.

GivenR⊆X×X(uma relação onX), defineRnby

R 0 =IXRn+1=R◦Rn.

Thetranstive closureR+ofRis dada por

R+=

⋃

n≥ 1

Rn.

Fact.R+é a menor relação transitiva containingR.

closureR Eflexivo e transitivo Deris dado por

R∗=

⋃

N≥ 0

Rn=R+. IX.

Fact.R∗é a menor relação transitiva e reflexiva containingR.

a relationR⊆X x Xis anequivalence relationif if it is reflexive, symmetric, and transitive.

Fact. A menor relação de equivalência que contém uma relação⊆X×Xis dada por

(R∪R− 1 )∗.

Um relationR⊆X×Xisantisymmetricif para allx,y∈X, se (x,y)∈Rand (y,x)∈R,thenx=y.

Um relationR⊆X×Xis apartial ordem, se é reflexiva, transitiva, e antisymmetic.

parcial orderR ⊆X×X é atotal ordem se para allx,y ∈X, um (x,y)∈ Ror(y,x)∈R.

2.2 Alfabetos, Cadeias de caracteres, Idiomas

Nossa visão de línguas é thata língua é um conjunto de cadeias de caracteres. Por sua vez, uma cadeia é uma consequência finita de letras de algum alfabeto. Estes conceitos são definidos rigorosamente da seguinte forma.

definição 2.1.AnalphabetΣ é qualquer coisa.

2.2. Alfabetos, cadeias de caracteres, línguas 11

muitas vezes escrevemos Σ = {a 1,…,ak}. As palavras são chamadas de palavras do alfabeto.Exemplo:Σ ={a}Σ ={a,b,c}Σ ={ 0 , 1 }Σ ={α,β,γ,δ,ǫ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ,ζ}string é Uma sequência finita de símbolos. Tecnicamente, é conveniente definir strings como funções. Para qualquer inteiro≥1, Vamos

={ 1 , 2 ,…, n},

e forn= 0, let=∅.

definição 2.2. Dado um alfabeto Σ, astring overΣ (ou simplesmente uma cadeia) de comprimento nisany função

u: →Σ.

the integern is theength of the stringu, and it is denoted as|u|. Whenn= 0, thespecial stringu: →Σ of length 0 is called theempty string, or null string, and is denotedasǫ.

Given a stringu: →Σ of lengthn≥1, u (i) is thei-th letter in the stringu. For sim-plicity of notation, we writeuiinstead ofu (i), and we denote the stringu=u(1) u(2)···u(n) as

u=u 1 u 2 ···un,

with eachui Σ Σ.

por exemplo, Se Σ = {A, b}andu: →Σ é definido tal thatu(1) =a,u(2) =b, andu (3) =a, We writeu=aba.

outros exemplos de cordas são

work, fun, gabuzomeuh

Strings of length 1 are functionsu: →Σ simply picking some elementu (1) =aiin Σ.Assim, identificaremos cada símbolo Σ Σ Com a correspondente cadeia de comprimento 1.

o conjunto de todas as cadeias sobre um alfabeto Σ, incluindo a cadeia vazia,é denotado como Σ∗.

2.2. ALFABETOS, CADEIAS de caracteres, IDIOMAS 13

Para a base casen= 0, sinceu 0 =ǫ, temos

u 0 u=ǫu=u=uǫ=uu 0.

Para o passo de indução, temos

un+1u= (unu)u, por definição, ofun+ = (uun)u pela hipótese de indução =u(unu) por associatividade ‘ a =uun+1, por definição, ofun+1.

definição 2.4.Dado um alfabeto Σ, dado quaisquer dois stringsu, v∈Σ we nós definimos as seguintes notas como se segue:

uis um prefixo de VIFF há algum∈Σ such tal que

v = uy.

uis um sufixo de sufixo de sufixo existe somex Σ Σ such tal que

v=xu.

uis um substrato de cheiff existem alguns x, y Σ Σ such tal que

v=xuy.Por exemplo,gais a prefixo de gabuzo, zois a sufixo de gabuzoandbuzis a substring ofgabuzo.Recall that a partial ordering≤ on a setS is a binary relation≤⊆ S×S which isreflexive, transitive, and antisymmetric.

os conceitos de prefixo, sufixo e substring definem relações Binárias Em Σ∗Na via obvious. Pode-se demonstrar que essas relações são ordenamentos parciais.

outra ordenação importante em strings é a ordenação lexicográfica (ou dicionário).

definição 2.5. Dado um alfabeto Σ = {a 1,…,ak}assumido totalmente ordenado tais thata 1 < um 2 <···< ak, tendo em conta as duas stringsu,v∈Σ∗, temos que definir thelexicographic orderingas seguinte:

> uv







(1) ifv=uy, para somey∈Σ∗, ou(2) ifu=xaiy,v=xajz,ai< aj,withai,aj∈Σ, e para somex,y,z∈Σ∗.

14 CHAPTER 2. Noções Básicas da teoria da linguagem FORMAL

a ideia é que nós digitalizamos simultaneamente da esquerda para a direita, comparando o themthsymboluminuto themth symbolvminv, começando Comm= 1. Se não surgir qualquer discrepância, esta é, se eles-o símbolo concorda com eles-o símbolo MPM= 1,…, / u/, thenué um prefixo de vand we declarate that uprecedesvin the lexicographic ordering. Caso contrário,para um whileuandvagree ao longo de um comum prefixx(possivelmente a cadeia vazia), e thenthere é aleftmost discrepância, o que significa que thatuis da formu=xaiyandvis de theformv=xajz, withai 6 =aj(andx,y,z∈Σ∗arbitrário). Em seguida, precisamos quebrar o laço, andto fazer isso, usamos o fato de que o symbolsa 1 < um 2 <···< ak são considerados (totalmente), ordenou, então, vemos que ofaiandajcomes primeiro, sayai< aj, e declaramos thatu=xaiyprecedesv=xajzin a ordenação lexicográfica.

Note que os casos (1) e (2) são mutuamente exclusivos. No caso (1),uis um prefixo ofv. No caso (2) v6uandu 6 =v.

por exemplo abb, gallhagergallier.

é bastante tedioso provar que a ordenação lexicográfica é, de facto, uma ordenação parcial.Na verdade, é uma ordenação total,o que significa que para qualquer dois stringsu, v Σ Σ Σ,eitheruv, orvu.

por conseguinte, um stringwrof é definido indutivamente da seguinte forma:

ǫR=ǫ,(ua)R=ura,

whena Σ Σ andu Σ Σ∗.

Por exemplo, reillag=gallierR.

Por settingu=ǫin (ua)R=auR,

sinceǫR=ǫanda=ǫa, obtemos

r= (ǫa)R=aǫR=aǫ=a,

namelyaR=pois alla∈Σ.

pode ser demonstrado por indução em|v|que

(uv)R=vRuR.

Um truque útil que reduz o incômodo notação ao fazer indução sobre stringsis a observação de que anonempty stringw∈Σ∗de lengthn+ 1 (n≥0) pode ser escrito como

> w=ua, para someu∈Σ∗e alguns symbola∈Σ, com|u|=n.

16 CAPÍTULO 2. FUNDAMENTOS DA LINGUAGEM FORMAL da TEORIA

IfXis não é o conjunto vazio, sincef:X→Nis uma injeção iff há um surjectionr:N→Xsuch thatr◦f= idX, o setXis contável iff há asurjectionfromNontoX.

Fact. Pode ser mostrado que uma setXis contável se é finito ou se ele está em bijectionwithN(caso em que ele é infinito).

veremos mais tarde quen×Nis contável. Como consequência, o conjunto dos números racionais é contável.

um conjunto é incontável se não for contável.

por exemplo, R (O conjunto de números reais) é incontável.Da mesma forma

(0,1) ={x R R / 0 < x < 1 }

é incontável. No entanto, há uma bijeção entre (0,1) andR(encontre uma!)O conjunto 2N de todos os subconjuntos destes incontáveis. Este é um caso especial do teorema de Cantor mencionado abaixo.

suponha|Σ|=kwith Σ ={a 1 ,…,ak}. Em primeiro lugar, observe que existem cadeias de comprimento de comprimento (kn+1-1)/(k−1) na maior parte dos casos Σ; quandok= 1, a segunda fórmula pode ser substituída por byn+ 1. De fato, uma vez que uma cadeia é uma função: {1 ,…, N} →Σ, o número de cadeias de comprimento é o número de funções de{ 1 ,…,n}To Σ, And since theardinality of Σ isk, there areknsuch functions (this is immediately shown by induction onn). Em seguida, o número de cordas de comprimento em mostnis

1 + k+k 2 +···+kn.

se k = 1, este número é n+ 1, e se k ≥ 2, como a soma de uma série geométrica, é(kn+1-1)/(k−1).

If Σ 6 =∅, then the set Σ∗of all strings over Σ is infinite and countable, as we now show by constructing an explicit bijection from Σ∗ontoN.

Ifk= 1 writea = a 1,and then

{a}∗={ǫ,A,aa, AAA,…,um,…}.

we have the bijectionn7→anfromNto{a}∗.Ifk≥2, then we can think of the string

u=ai 1 · * ain

as a representation of the integerv (u) in basekshifted by(kn−1)/(k−1), with

2.2. ALFABETOS, CADEIAS de caracteres, IDIOMAS 17

ν(u) =i = 1 kn− 1 +i 2 kn− 2 +···+em 1 de k+em

=

kn− 1 k− 1

• (i 1 -1)kn− 1 +···+ (em− 1 (-1)k+in− 1.

(and witv (ǫ) = 0), where 1≤IJ≤kforj= 1,…, n.

we leave it as an exercise to show thatv: Σ∗→Nis a bijection. Findingexplicitly (thatis, a formula) for the inverse ofvis surprisingly difficult.

in fact,ν corresponds to the enumeration of Σ∗where uprecedesv if / u/ < / v/, anduprecedesvin the lexicographic ordering if|u|=|v|. É fácil verificar que a aboverelation (uprecedesv) é uma ordem total.

Por exemplo, o ifk= 2 e se podemos escrever Σ ={a,b}, então a enumeração começa com

ǫ,0a, b,1 , 2 ,aa, ab, ba, bb,3 , 4 , 5 , 6 ,aaa, aab, aba, abb, baa, bab, bba, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14

Para obter a próxima linha, concatenateaon a esquerda e, em seguida, concatenatebon a esquerda. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.Funciona!

por outro lado, Se Σ 6 =∅, O conjunto 2σσ de todos os subconjuntos de Σ ∗ (todas as línguas) é incontável.Na verdade, podemos mostrar que não há nenhuma surjeção do ponto 2σσ Primeiro, vamos mostrar que não há nenhuma surjeção de Σ∗Para 2σσ. Este é um caso especial do teorema de Cantor.Nós afirmamos que se não há surjeção de Σ∗Para 2σσ, então não há surjeção denonto 2σσ também.

Proof. Suponha por contradição que existe um surjetiong:n→ 2 Σ ∗ . Mas, Se Σ 6 =∅, entãoσσ é infinito e contável, assim temos a bijetionv: Σ→ → N. Então a composição

Σ∗ ν // n

g / / 2 Σ Σ

é uma surjeção, porque a bijetionvis uma surjeção,gis uma surjeção, e a composição de surjeções é uma surjeção, contradizendo a hipótese de que não há surjeção deσ ∗para 2σσ .

2.3. Operações nas línguas 19

2.3 operações nas línguas

uma forma de construir línguas mais complexas a partir de línguas mais simples é combiná-las utilizando várias operações. Em primeiro lugar, revisamos as operações set-teóricas de união, interseção e complementação.

Dado algum alfabeto Σ, para quaisquer dois languagesL 1 ,L 2 sobre Σ, theunionL 1 ∪L 2 aaf 1andL 2 é a linguagem

L 1 ∪L 2 ={w∈Σ∗|w∈L 1 ou o w∈L 2 }.

TheintersectionL 1 ∩L 2 aaf 1 andL 2 é a linguagem

L 1 ∩L 2 ={w∈Σ∗|w∈L 1 e w∈L 2 }.

a diferença 1-L 2 de l 1 e L 2 é a língua

L 1-L 2 = {w Σ Σ Σ|w 1 L 1 e w/. L 2}.

a diferença também é chamada de complemento terelativo.

um caso especial da diferença é obtido quando L1 = Σ,, caso em que definimos o termo de uma língua

L={w Σ Σ Σ|w / / L}.

as operações acima não usam a estrutura das cordas. As operações a seguir useconcatenação.

definição 2.8.Dado um alfabeto Σ, para quaisquer dois languagesL 1 ,L 2 sobre Σ, theconcatenationL 1 L 2 aaf 1 andL 2 é a linguagem

L 1 L 2 ={w∈Σ∗|∃u∈L 1 ,∃v∈L 2 , w=uv}.

para qualquer língua, definimos as seguintes definições:

l 0 ={ǫ}, Ln+1=LnL (n≥0).

Por settingn= 0 inLn+1=LnL, sinceL 0 ={ǫ}, obtemos

1 L =L0+1=L 0 L={ǫ}L=L,

soL 1 =L.

20 CAPÍTULO 2. FUNDAMENTOS DA LINGUAGEM FORMAL da TEORIA

As seguintes propriedades são facilmente verificada:

L∅=∅,∅L=∅,L{ǫ}=L{ǫ}L=L,(L-1 ∪{ǫ})L 2 =L 1 L 2 ∪L 2 ,L 1 L 2 ∪{ǫ}) =L 1 L 2 ∪L 1 ,LnL=LLn.

em geral, L 1 L 26 =L 2 L 1.So longe, as operações que introduzimos, exceto a complementação (sinceL = Σ∗ – Lis infinite ifLis finito e Σ é não vazio), preservam a finitude das linguagens. Não é o caso das duas próximas operações.

definição 2.9.Dado um alfabeto Σ, Para qualquer languageLover Σ, theKleene∗ – closureL∗ofLis a língua

l∗=