Aula0.2 LingFormais PDs

Prévia do material em texto

Linguagens Formais e Problemas de Decisa˜o
Ma´rio S. Alvim
(msalvim@dcc.ufmg.br)
Fundamentos de Teoria da Computac¸a˜o (FTC)
DCC-UFMG
(2018/01)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 1 / 27
Introduc¸a˜o
No dia-a-dia estamos acostumados com linguagens naturais, como
portugueˆs, ingleˆs, franceˆs, ...
Estas linguagens nos permitem descrever objetos precisamente, atrave´s de
cadeias (ou palavras).
Aqui vamos estudar linguagens formais, que sa˜o conjuntos de cadeias
matematicamente constru´ıdos para descrever objetos abstratos.
Uma das aplicac¸o˜es mais relevantes de linguagens formais em cieˆncia da
computac¸a˜o e´ a definic¸a˜o de linguagens de programac¸a˜o.
Voceˆ ja´ pensou que existe uma “linguagem dos programas em C”, e que cada
“cadeia” e´ um programa va´lido em C?
Como definimos esta linguagem? Qual e´ a sua “grama´tica”?
Como aqui vamos lidar apenas com linguagens formais, podemos nos referir a
elas apenas como “linguagens”.
Em particular, vamos ver como linguagens formais esta˜o associadas a
problemas de decisa˜o, que sa˜o um dos cernes da cieˆncia da computac¸a˜o.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 2 / 27
Linguagens Formais
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 3 / 27
Linguagens: Conceitos fundamentais
Um alfabeto e´ um conjunto finito na˜o-vazio de elementos chamados
s´ımbolos.
Exemplo 1 Exemplos de alfabetos:
1 {0, 1} e´ o alfabeto bina´rio,
2 {a, b, c, . . . , z} e´ o alfabeto de letras latinas minu´sculas,
3 {a1, a2, a3} e´ um alfabeto terna´rio (de apenas treˆs s´ımbolos),
4 {�,4,©,×} e´ o alfabeto das 4 teclas principais do controle do Playstation,
5 o conjunto de caracteres do teclado e´ um alfabeto.
�
Notac¸a˜o: Normalmente usamos a letra Σ para denotar um alfabeto.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 4 / 27
Linguagens: Conceitos fundamentais
Uma cadeia (ou palavra) de um alfabeto Σ e´ uma sequeˆncia finita de
s´ımbolos de Σ.
Exemplo 2 Exemplos de cadeias no alfabeto {0, 1}:
1 0
2 011
3 1101010001
4 �
�
O s´ımbolo � denota a cadeia vazia, ou seja, a cadeia formada por 0 s´ımbolos.
|w | denota o tamanho (i.e., o nu´mero de s´ımbolos) da cadeia w .
Exemplo 3
1 |0| = 1
2 |011| = 3
3 |1101010001| = 10
4 |�| = 0
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 5 / 27
Linguagens: Conceitos fundamentais
an denota n s´ımbolos a em sequeˆncia.
Exemplo 4
1 14 = 1111 2 10 = � 3 a2b3a2 = aabbbaa
�
Σ∗ (leˆ-se “sigma estrela”) denota o conjunto de todas as cadeias que podem
ser formadas com o alfabeto Σ.
Exemplo 5
1 {a}∗ = {�, a, aa, aaa, a4, a5, . . .}
2 {0, 1}∗ = {�, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, . . .}
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 6 / 27
Linguagens: Conceitos fundamentais
Uma linguagem sobre um alfabeto Σ e´ um subconjunto de Σ∗.
Exemplo 6 Exemplos de linguagens sobre o alfabeto {0, 1}:
1 {0, 1, 00, 11}
2 ∅
3 {�}
4 {�, 0, 1}
5 {�, 02, 04, 06, 08, 010, . . .}
6 {w ∈ Σ∗ | |w | e´ mu´ltiplo de 3}
7 {0n1n | n ≥ 0}
8 {0n | n e´ um nu´mero primo}
9 {0, 1}∗
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 7 / 27
Linguagens: Conceitos fundamentais
Como linguagens sa˜o conjuntos, operac¸o˜es de conjuntos tambe´m se aplicam
a linguagens.
Sejam L1 e L2 linguagens sobre os alfabetos Σ1 e Σ2, respectivamente.
Enta˜o:
L1 ∪ L2 e´ uma linguagem sobre o alfabeto Σ1 ∪ Σ2,
L1 ∩ L2 e´ uma linguagem sobre o alfabeto Σ1 ∩ Σ2,
L1 = {w ∈ Σ∗1 | w /∈ L1} e´ uma linguagem sobre o alfabeto Σ1,
L1 − L2 = L1 ∩ L2 e´ uma linguagem sobre o alfabeto Σ1,
P(L1) e´ um conjunto de linguagens sobre Σ1,
P(Σ∗1 ) e´ o conjunto de todas as linguagens sobre Σ1.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 8 / 27
Linguagens: Conceitos fundamentais
Exemplo 7 Sejam as linguagens
L1 = {w ∈ {0, 1}∗ | |w | e´ par}
e
L2 = {w ∈ {0, 1}∗ | w comec¸a com 0}.
1 L1 ∪ L2 = {w ∈ {0, 1}∗ | |w | e´ par ou w comec¸a com 0}.
2 L1 ∩ L2 = {w ∈ {0, 1}∗ | |w | e´ par e w comec¸a com 0}.
3 L1 = {w ∈ {0, 1}∗ | |w | e´ ı´mpar}.
4 L1 − L2 = {w ∈ {0, 1}∗ | |w | e´ par e w na˜o comec¸a com 0}.
5 P(L1) e´ o conjunto de todas as linguagens em que as cadeias da linguagem
teˆm tamanho par.
6 P({0, 1}∗) e´ o conjunto de todas as linguagens bina´rias.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 9 / 27
Linguagens: Conceitos fundamentais
Dadas duas cadeias x = a1a2 . . . an e y = b1b2 . . . bm, sua concatenac¸a˜o e´
xy = a1a2 . . . anb1b2 . . . bm.
Exemplo 8
1 Se x = 010 e y = 1111, enta˜o
xy = 0101111.
2 Para toda cadeia x :
�x = x� = x .
3 Para toda cadeia x , y , z :
(xy)z = x(yz) = xyz .
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 10 / 27
Linguagens: Conceitos fundamentais
Um prefixo de uma cadeia w e´ uma cadeia x tal que w = xy para algum y .
Um sufixo de uma cadeia w e´ uma cadeia y tal que w = xy para algum x .
Uma subcadeia de uma cadeia w e´ uma cadeia z tal que w = xzy para
algum x , y .
Exemplo 9
1 Prefixos de abc: �, a, ab, abc.
2 Sufixos de abc: �, c, bc, abc.
3 Subcadeias de abc: �, a, b, c, ab, bc, abc. �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 11 / 27
Linguagens: Conceitos fundamentais
O reverso de uma cadeia w = a1a2 . . . an e´ a cadeia w
R = an . . . a2a1.
Exemplo 10
1 abcR = cba 2 aR = a 3 �R = �
�
Um pal´ındromo e´ uma cadeia w tal que w = wR .
Exemplo 11 As seguintes cadeias sa˜o pal´ındromos.
1 01010 2 a 3 �
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 12 / 27
Linguagens: Conceitos fundamentais
Dadas duas linguagens L1 e L2, sua concatenac¸a˜o e´
L1L2 = {xy | x ∈ L1 e y ∈ L2}.
Exemplo 12 Sejam
L1 = {w ∈ {0, 1}∗ | |w | = 5}
e
L2 = {0y | y ∈ {0, 1}∗}.
1 L1L1 = {w ∈ {0, 1}∗ | |w | = 10}
2 L1L2 = {w ∈ {0, 1}∗ | |w | ≥ 6 e o sexto s´ımbolo de w e´ 0}
3 L2L1 = {w ∈ {0, 1}∗ | |w | ≥ 6 e w comec¸a com 0}
4 L2L2 = {0y | y ∈ {0, 1}∗ e y conte´m pelo menos um 0}
5 L1{�} = L1
6 L1∅ = ∅
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 13 / 27
Linguagens: Conceitos fundamentais
Ln denota a linguagem L concatenada com ela mesma n vezes.
Em particular,
L1 = L L0 = {�}
Exemplo 13
1 {0, 1}3 = {000, 001, 010, 011, 101, 101, 110, 111}
2 {aa, b}2 = {aaaa, aab, baa, bb}
�
O fecho de Kleene, ou estrela, de uma linguagem L e´
L∗ = L0 ∪ L1 ∪ L2 ∪ L3 ∪ L4 . . .
O fecho positivo de Kleene, ou mais, de uma linguagem L e´
L+ = LL∗ = L1 ∪ L2 ∪ L3 ∪ L4 . . .
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 14 / 27
Linguagens: Conceitos fundamentais
Exemplo 14 Exemplos de fechos de Kleene e fechos positivos de Kleene:
1 {0, 1}∗ = {�, 0, 1, 00, 01, 10, 11, 000, 001, . . .}
2 {0}∗ = {0n | n ≥ 0}
3 {0}+ = {0n | n ≥ 1}
4 {00}∗ = {w ∈ {0}∗ | |w | e´ par}
5 {00}+ = {w ∈ {0}∗ | |w | e´ par e |w | ≥ 2}
6 {01, 1}∗ = {w ∈ {0, 1}∗ | todo 0 em w e´ seguido de pelo menos um 1}
7 {�, 00, 11}∗ = {�, 00, 11}+ = {�} ∪ {00, 11}+
8 {�}∗ = {�}+ = {�}
9 ∅∗ = {�}
10 ∅+ = ∅
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 15/ 27
Linguagens: Conceitos fundamentais
Como todo alfabeto Σ e´ finito, o conjunto Σ∗ e´ enumera´vel. (Por queˆ?)
Como toda linguagem e´ um subconjunto de Σ∗,
toda linguagem e´ enumera´vel.
Logo, e´ poss´ıvel dar uma definic¸a˜o recursiva de linguagens.
Mais para frente veremos como isso e´ feito, usando o conceito de
grama´ticas.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 16 / 27
Problemas de Decisa˜o
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 17 / 27
Problemas de decisa˜o
Um problema de decisa˜o (PD) e´ uma questa˜o que:
1. faz refereˆncia a um conjunto de paraˆmetros, e que
2. para cada atribuic¸a˜o de valores a todos os paraˆmetros, possui como resposta
“SIM” ou “NA˜O”.
Exemplo 15 Exemplos de problemas de decisa˜o:
1 Determinar se um natural n e´ primo. (1 paraˆmetro: n.)
2 Determinar se x + y = z para x , y , z ∈ Z. (3 paraˆmetros: x , y , z .)
3 Determinar se 234 456 777 e´ primo. (0 paraˆmetros.)
4 Determinar se existe um ciclo de tamanho pelo menos k num grafo G . (2
paraˆmetros: k, G .)
5 Determinar se uma cadeia w pertence a uma linguagem L. (2 paraˆmetros: w ,
L.)
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 18 / 27
Problemas de decisa˜o
Uma instaˆncia de um PD e´ uma questa˜o obtida ao se atribu´ırem a todos os
paraˆmetros do PD valores espec´ıficos.
Exemplo 16 O PD de se determinar se um natural n e´ primo tem infinitas
instaˆncias:
Determinar se 0 e´ primo.
Determinar se 1 e´ primo.
Determinar se 2 e´ primo.
Determinar se 3 e´ primo.
. . . �
Exemplo 17 O PD de se determinar se 234 456 777 e´ primo tem uma u´nica
instaˆncia. �
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 19 / 27
Problemas de decisa˜o
Uma soluc¸a˜o para um problema de decisa˜o e´ um procedimento (ou
algoritmo) que retorna a resposta correta para toda e qualquer instaˆncia do
problema.
Um PD e´ decid´ıvel se ele tem soluc¸a˜o, e indecid´ıvel em caso contra´rio.
Todo PD com finitas instaˆncias e´ decid´ıvel. (Por queˆ?)
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 20 / 27
Linguagens Formais e
Problemas de Decisa˜o
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 21 / 27
Linguagens Formais e Problemas de Decisa˜o
Aqui vamos nos concentrar em um tipo muito importante de problema de
decisa˜o:
“A cadeia w pertence a` linguagem L?”
Um algoritmo capaz de responder corretamente a todas as instaˆncias de w do
PD acima e´ um decisor para a linguagem L.
Mais para a frente no curso vamos estudar tambe´m o conceito de um
reconhecedor para a linguagem, que e´ um algoritmo que:
1. responde SIM para toda cadeia pertencente a` linguagem,
2. para cadeias na˜o-precentes a` linguagem, ou responde NA˜O, ou apenas “se cala”
e na˜o responde nada.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 22 / 27
Linguagens Formais e Problemas de Decisa˜o
Decidir linguagens e´ equivalente a resolver problemas de decisa˜o.
Ou seja, existe uma correspondeˆncia entre um decisor para uma linguagem
e uma soluc¸a˜o para um problema de decisa˜o com um
nu´mero enumera´vel de instaˆncias.
Para ver a equivaleˆncia, primeiro introduzimos a notac¸a˜o 〈x〉 para a
representac¸a˜o de um objeto x como uma cadeia de um alfabeto Σ.
Assim, um problema de decisa˜o com um nu´mero enumera´vel de instaˆncias
“A resposta para o PD com paraˆmetros x e´ SIM ou NA˜O?”
e´ equivalente ao problema de linguagem
“A cadeia 〈x〉 pertence a` linguagem L?”
para uma linguagem L apropriada.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 23 / 27
Linguagens Formais e Problemas de Decisa˜o
Exemplo 18 O problema de decisa˜o
“n e´ primo, para n ∈ N?”
e´ equivalente ao problema de decidir a pertineˆncia de uma cadeia a` linguagem
Lprimos = {〈n〉 | n ∈ N e n e´ primo}.
Uma maneira de fazer isto e´ definir a seguinte representac¸a˜o para os naturais
〈n〉 = 0n,
de forma que 〈1〉 = 0, 〈5〉 = 00000, 〈0〉 = 00 = �, etc.
Assim, o problema de decisa˜o acima e´ equivalente ao problema de decidir a
pertineˆncia de uma cadeia a` linguagem
Lprimos = {0n | n e´ primo}.
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 24 / 27
Linguagens Formais e Problemas de Decisa˜o
Exemplo 19 O problema de decisa˜o
“x + y = z , para x , y , z ∈ Z?”
e´ equivalente ao problema de decidir a pertineˆncia de uma cadeia a` linguagem
Lx+y=z = {〈x , y , z〉 | x , y , z ∈ Z e x + y = z}.
�
Exemplo 20 O problema de decisa˜o
“O grafo G possui um ciclo de tamanho pelo menos k?”
e´ equivalente ao problema de decidir a pertineˆncia de uma cadeia a` linguagem
Lgrafo = {〈G , k〉 | G e´ um grafo com um ciclo de tamanho pelo menos k}.
�
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 25 / 27
Linguagens Formais e Problemas de Decisa˜o
Como dissemos, reconhecer linguagens e´ equivalente a resolver problemas de
decisa˜o com um nu´mero enumera´vel de instaˆncias.
Neste curso vamos construir ma´quinas que decidem se cadeias pertencem ou
na˜o a uma dada linguagem.
Cada ma´quina uma destas ma´quinas e´ uma soluc¸a˜o para o problema de
decisa˜o equivalente a` linguagem!
Enta˜o, e´ importante entender quais linguagens podem ser decididas (ou
reconhecidas) por quais ma´quinas, pois assim estamos estudando quais
problemas de decisa˜o teˆm soluc¸a˜o (ou teˆm soluc¸a˜o parcial)!
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 26 / 27
A Hierarquia de Chomsky
As linguagens podem ser
organizadas em n´ıveis de
complexidade.
A hierarquia de Chomsky
organiza as linguagens em
termos da complexidade as
ma´quinas necessa´rias para
dedicid´ı-las/reconheceˆ-las.
Neste curso vamos comec¸ar
com as ma´quinas mais sim-
ples, e ir subindo na Hierar-
quia de Chomsky.
Ma´rio S. Alvim (msalvim@dcc.ufmg.br) Linguagens Formais e Problemas de Decisa˜o DCC-UFMG (2018/01) 27 / 27