Являются ли эти программы Python для определения двусмысленности конечной грамматики правильной?

Question

Я делаю Udacity CS262 и для проблемы с обнаружением неоднозначности. Я не уверен, что мое решение правильно, и я не уверен, правильно ли это официальное решение.

Краткое описание проблемы: Напишите функцию isambig (грамматика, начало, строка), которая использует конечную контекстную свободную грамматику (закодированную как словарь python), символ начала грамматики и строку. Если есть два дерева синтаксического анализа, ведущих к строке, то грамматика неоднозначна (или, по крайней мере, это мое понимание двусмысленности - пожалуйста, исправьте меня, если я ошибаюсь). Если грамматика неоднозначна, верните True. Else return False.

Тестовые:

grammar1 = [ 
     ("S", [ "P", ]), 
     ("S", [ "a", "Q", ]) , 
     ("P", [ "a", "T"]), 
     ("P", [ "c" ]), 
     ("Q", [ "b" ]), 
     ("T", [ "b" ]), 
     ] 
print isambig(grammar1, "S", ["a", "b"]) == True 
print isambig(grammar1, "S", ["c"]) == False 

grammar2 = [ 
     ("A", [ "B", ]), 
     ("B", [ "C", ]), 
     ("C", [ "D", ]), 
     ("D", [ "E", ]), 
     ("E", [ "F", ]), 
     ("E", [ "G", ]), 
     ("E", [ "x", "H", ]), 
     ("F", [ "x", "H"]), 
     ("G", [ "x", "H"]), 
     ("H", [ "y", ]), 
     ] 
print isambig(grammar2, "A", ["x", "y"]) == True 
print isambig(grammar2, "E", ["y"]) == False 

grammar3 = [ # Rivers in Kenya 
     ("A", [ "B", "C"]), 
     ("A", [ "D", ]), 
     ("B", [ "Dawa", ]), 
     ("C", [ "Gucha", ]), 
     ("D", [ "B", "Gucha"]), 
     ("A", [ "E", "Mbagathi"]), 
     ("A", [ "F", "Nairobi"]), 
     ("E", [ "Tsavo" ]), 
     ("F", [ "Dawa", "Gucha" ]) 
     ] 
print isambig(grammar3, "A", ["Dawa", "Gucha"]) == True 
print isambig(grammar3, "A", ["Dawa", "Gucha", "Nairobi"]) == False 
print isambig(grammar3, "A", ["Tsavo"]) == False 

Я добавил свой собственный тестовый случай. Я не уверен, что это правильно, но я вижу только одно дерево разбора, ведущее к строке «a b», поэтому строка не доказывает двусмысленность грамматики. И я не верю, что грамматика неоднозначна.

grammar4 = [ # Simple test case 
     ("S", [ "P", "Q"]), 
     ("P", [ "a", ]), 
     ("Q", [ "b", ]), 
     ] 
print isambig(grammar4, "S", ["a", "b"]) == False 

Вот "официальная" программа:

def expand(tokens_and_derivation, grammar): 
    (tokens,derivation) = tokens_and_derivation 
    for token_pos in range(len(tokens)): 
     for rule_index in range(len(grammar)): 
      rule = grammar[rule_index] 
      if tokens[token_pos] == rule[0]: 
       yield ((tokens[0:token_pos] + rule[1] + tokens[token_pos+1:]), derivation + [rule_index]) 

def isambig(grammar, start, utterance): 
    enumerated = [([start], [])] 
    while True: 
     new_enumerated = enumerated 
     for u in enumerated: 
      for i in expand(u,grammar): 
       if not i in new_enumerated: 
        new_enumerated = new_enumerated + [i] 

     if new_enumerated != enumerated: 
      enumerated = new_enumerated 
     else: 
      break 
    result = [xrange for xrange in enumerated if xrange[0] == utterance] 
    print result 
    return len(result) > 1 

Вот моя собственная, гораздо больше программы:

def expand(grammar, symbol): 
    result = [] 
    for rule in grammar: 
     if rule[0] == symbol: 
      result.append(rule[1]) 
    return result 

def expand_first_nonterminal(grammar, string): 
    result = [] 
    for i in xrange(len(string)): 
     if isterminal(grammar, string[i]) == False: 
      for j in expand(grammar, string[i]): 
       result.append(string[:i]+j+string[i+1:]) 
      return result 
    return None 

def full_expand_string(grammar,string, result): 
    for i in expand_first_nonterminal(grammar,string): 
     if allterminals(grammar,i): 
      result.append(i) 
     else: 
      full_expand_string(grammar,i,result) 

def isterminal(grammar,symbol): 
    for rule in grammar: 
     if rule[0] == symbol: 
      return False 
    return True 

def allterminals(grammar,string): 
    for symbol in string: 
     if isterminal(grammar,symbol) == False: 
      return False 
    return True 

def returnall(grammar, start): 
    result = [] 
    for rule in grammar: 
     if rule[0] == start: 
      if allterminals(grammar,rule[1]): 
       return rule[1] 
      else: 
       full_expand_string(grammar, rule[1], result) 
    return result 

def isambig(grammar, start, utterance): 
    count = 0 
    for i in returnall(grammar,start): 
     if i == utterance: 
      count+=1 
    if count > 1: 
     return True 
    else: 
     return False 

Теперь моя программа проходит все тестовые случаи, включая один Я добавил (grammar4), но официальное решение проходит все тестовые примеры, кроме тех, которые я добавил. Мне кажется, что либо тестовый пример неправильный, либо официальное решение ошибочно.

Является ли официальное решение правильным? Правильно ли мое решение?

Answer 1

Мне кажется, что grammar4 не является двусмысленным. Существует только один дерево разбора:

S -> PQ 
P -> a 
Q -> b 

    S 
    | 
___|____ 
P  Q 
|  | 
a  b 

Однако официальная программа говорит, что она является неоднозначной, поскольку он использует правила P -> aQ -> b и последовательно:

[(['a', 'b'], [0, 1, 2]), (['a', 'b'], [0, 2, 1])] 

(сейчас есть два rule- последовательности 0,1,2 и 0,2,1.)

Таким образом, «официальная» программа, как представляется, неправильно определяет grammar4 как ambiguou s.

UPDATE: я просматривал свой код и сделал несколько тестов, и, кроме не обрабатывает рекурсии (официальная версия не обрабатывает рекурсии либо), ваша программа, кажется, правильно различать неоднозначным и недвусмысленной.

Простой тест:

grammar5 = [ 
      ("S", ["A", "B"]), 
      ("S", ["B", "A"]), 
      ("A", ["a"]), 
      ("B", ["a"]), 
      ] 
print(isambig(grammar5, "S", ["a", "a"])) 

S -> AB 
S -> BA 
A -> a 
B -> a 

    S 
    | 
___|____ 
A  B 
|  | 
a  a 

    S 
    | 
___|____ 
B  A 
|  | 
a  a 

Ваша версия возвращает "неоднозначной" (как это делает "официальную" версию.)

Если удалить ("S", ["B", "A"]), ваша версия правильно переключатели «не неоднозначным», в то время как другая версия по-прежнему возвращает «неоднозначной» (мы вернулись в случае grammar4.)

Может быть кто-то другой (с немного больше опыта, чем у меня) может вступать в

UPDATE 2:. Ira Baxter отметил, что это является неразрешимой проблемой, является ли неоднозначной контекстно-свободной грамматики.

Смотрите также How is proving a context free language to be ambiguous undecidable?