Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
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 decisor para uma linguagem e soluc¸a˜o para um problema de decisa˜o. 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, qualquer problema de decisa˜o “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. 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
Compartilhar