prob-indec

Prévia do material em texto

Indecidibilidade da Ambiguidade para CFGs
1. Nossa motivação para definir o problema de correspondência de Post
(PCP) e demonstrar sua indecidibilidade foi a de que ficasse
facilitada a argumentação sobre a indecidibilidade de problemas que
não tem a “cara” de uma máquina de Turing.
2. O problema de decisão sobre a ambiguidade de uma gramática livre
de contexto (“context free grammar” – CFG) é um destes problemas.
Uma CFG é dita ambı́gua se, para alguma string que pertença a
linguagem definda pela CFG, existir mais de uma derivação.
3. Para abreviar, chamaremos o problema de decisão da ambiguidade de
uma CFG de ACFG. O ACFG pode ser reduzido ao PCP seguindo a
seguinte intuição:
(a) Construiremos uma gramática a partir da união de duas outras
gramáticas que são, por construção, não-ambı́guas.
(b) As produções de cada uma destas duas gramáticas é construı́da a
1
partir de uma string do PCP, ou seja, a partir de
� � � � � � � ��� � � � � � e 	 � 
 � � 
 � ��� � � 
 � � , e a partir de sı́mbolos
de ı́ndice � � 
 � � 
� � � 
 � � que representam os ı́ndices de uma
solução do PCP.
(c) A construção da gramática é de tal forma que se existir uma
solução para o PCP existirão também duas derivações para uma
string que pertence a linguagem induzida pela gramática
resultante da união das suas gramáticas construı́das a partir de �
e 	 .
4. As gramáticas � � e � � tem a seguinte forma geral:
� � � � � � � � � � � � � � � � � � � � � � � �
� � � � � � � � � � � � � � � � � �
� � é construı́da de forma análoga, porém utilizando a string
 � � 
 � � � � � 
 � � ao invés de � � � � � ��� � � � � � .
2
5. Note que a forma das strings derivadas da gramática � � (resp. � � ) é
� � � � � ��� � � � � � � � � � � � � � � � � � (resp. 
 � � 
 � � � � � 
 � � � � � � � � � � � � � � ).
6. Mais ainda, � � e � � não são ambı́guas: uma produção � � � � � em
� � é utilizada quando o passo de derivação não for o último e � � � �
quando for o último. O mesmo raciocı́nio vale para � � .
7. � � e � � são unidas, formando � � � , da seguinte maneira:
(a) Adiciona-se a produção inicial � � � � 	 .
(b) Adicionam-se as produções de � � .
(c) Adicionam-se as produções de � � .
8. Como dito anteriormente, � � � será ambı́gua se houver uma solução
para o PCP � � 
 	 � . Se houver uma solução para � � 
 	 � então
� � � � � ��� � � � � � � � � � � � � � � � � � � 
 � � 
 � � � � � 
 � � � � � � � � � � � � � � sendo
possı́vel derivar a mesma string a partir do ramo � � da gramática
assim como do ramo � � da gramática.
3
Teorema 1 � � � é ambı́gua sss a instância (A,B) do PCP tem
solução.
Prova.
( � ) Se � � � é ambı́gua existem � � � � � � � � � � � � � � � � � � � � � � � � e
 � � 
 � � � � � 
 � � � � � � � � � � � � � � representando a mesma string. Se
representam a mesma string então � � � e � � � � � � � � � � � � é uma
solução para o PCP pois � � � � � ��� � � � � � � 
 � � 
 � ��� � � 
 � � .
( � ) Se � � 
 	 � tem solução, por exemplo � � � � � � � � � então
� � � � � ��� � � � � � � � � � � � � � � � � � � 
 � � 
 � � � � � 
 � � � � � � � � � � � � � � e a
mesma string pode ser derivada de duas formas por � � � .
4