Построить диаграмму состояний для ТМ - PullRequest
Новая
       60

Построить диаграмму состояний для ТМ

1 голос
/ 13 июня 2019

Рассмотрим язык ? = {a 3 n ;п> = 0}

1 Ответ

1 голос
/ 13 июня 2019

Моя стратегия заключается в том, чтобы искать части строк, чтобы увидеть, как они связаны.Я вижу три основные части этой строки:

  1. строка a: возможно, нет, но любое число
  2. строка b: такое же, как число a, плюс два
  3. строка c: любое число, кроме как минимум одного

Мы видим, что числа a и b связаны, но число c полностью не связано.Если мы можем получить грамматику только для первых двух частей, мы можем объединить символ, который является начальным символом грамматики для другой части, и получить грамматику для всех трех частей.В символах: 

S   -> S' S''
S'  -> (first two parts)
S'' -> (third part)

Давайте сделаем грамматику для третьей части, первой с c.Самая короткая строка, которая принадлежит этой части, является строкой c длины один;Итак, мы можем добавить производство, как S'' -> c.Чтобы получить более длинную строку из заданной, которая уже является допустимой третьей частью, мы можем добавить еще одну c;это предполагает производство S'' -> S'' c.Фактически, мы можем подтвердить, что эти два производства позволяют нам генерировать все действительные третьи части.Наша грамматика выглядит следующим образом: 

S   -> S' S''
S'  -> (first two parts)
S'' -> S'' c | c

Теперь давайте попробуем первые две части.На самом деле мы можем также разбить это на две части: часть, которая соответствует a и b, и часть, которая является дополнительными +2 экземплярами b.Теперь наша грамматика выглядит следующим образом: 

    S -> S' S''
   S' -> S''' S''''
  S'' -> S'' c | c 
 S''' -> (matched a and b)
S'''' -> bb

Чтобы получить грамматику для совпадающих a и b, единственной оставшейся части, мы можем использовать ту же процедуру, что и для третьей части.Самая короткая строка из совпадающих a и b является пустой строкой (здесь мы не требуем, чтобы число было строго положительным);это подразумевает S''' -> e.Если задана правильная строка совпадений a и b, вы можете получить следующую, добавив a впереди и ab сзади: S''' -> a S''' b.Наша законченная грамматика выглядит следующим образом: 

    S -> S' S''
   S' -> S''' S''''
  S'' -> S'' c | c 
 S''' -> a S''' b | e
S'''' -> bb

Теперь, чтобы упростить эту грамматику, мы можем исключить пустые производства и удалить нетерминальные символы, такие как S '' '', которые просто заменяют строку терминалов.Чтобы устранить пустое производство, нам нужно добавить дополнительное производство с удаленным S '' 'везде, где есть существующее производство с S' ''.Есть два таких производства, поэтому мы добавим два производства и удалим пустое: 

    S -> S' S''
   S' -> S''' S'''' | S''''
  S'' -> S'' c | c 
 S''' -> a S''' b | ab
S'''' -> bb

Избавиться от S '' '' легко, просто замените любой его экземпляр на bb: 

    S -> S' S''
   S' -> S''' bb | bb
  S'' -> S'' c | c 
 S''' -> a S''' b | ab

Это должно более или менее сделать это.Доказательство оставлено в качестве упражнения.

...