Выполнить алгоритм Маркова
Задача:
Создайте интерпретатор для алгоритма Маркова .
Правила имеют синтаксис:
В каждой строке есть одно правило.
Если есть . (период), присутствующий до
Набор правил состоит из последовательности правил с необязательными комментариями.
Rulesets
Используйте следующие тесты для записей:
Правила 1:
Этот файл правил извлекается из Википедии: http://en.wikipedia.org/wiki/Markov_AlgorithmA -> яблоко B -> сумка S -> магазин T -> магазин -> мой брат никогда не использовалось -> .terminating rule
Пример текста:
I bought a B of As from T S.
Должен генерировать вывод:
I bought a bag of apples from my brother.
Правила 2:
Проверка правила завершения
Немного изменен из правил на WikipediaA -> apple B -> сумка S -> .shop T -> магазин -> мой брат никогда не использовалось -> .terminating rule
Пример текста:
I bought a B of As from T S.
Должна генерировать:
I bought a bag of apples from T shop.
Правила 3:
Это проверяет правильный порядок замещения и может задерживать простые подпрограммы на основе регулярного выражения, если специальные символы регулярного выражения не экранируются.
BNF Синтаксические правила тестированияA -> apple WWWW -> с Багаж -> ->. * B -> сумка ->. * -> деньги W -> WW S -> .shop T -> магазин -> мой брат никогда не использовалось -> .terminating rule
Пример текста:
I bought a B of As W my Bgage from T S.
Должна генерировать:
I bought a bag of apples with my money from T shop.
Правила 4:
Это проверяет правильность порядка сканирования правил и может задерживать процедуры замены, которые сканируются в неправильном порядке. Он реализует общий механизм унарного умножения. (Обратите внимание, что входное выражение должно быть помещено в символы подчеркивания в этой реализации.)
## Unary Multiplication Engine, для тестирования алгоритмов Алгоритма Маркова ## Донал Стипендиаты. Унарное сложение engine_ + 1 -> _1 + 1 + 1 -> 11+ Переход для преобразования из расщепления умножения в обычный addition1! -> 1 ,! ->! + _! -> _ Унарное умножение путем дублирования левой стороны, правое время 1 * 1 -> x, @ y 1x -> xX X, -> 1,1 X1 -> 1X _x -> _X , х ->, X y1 -> 1y y_ -> _ Следующая фаза применения 1 @ 1 -> x, @ y 1 @ _ -> @_ , @ _ ->! _ ++ -> + Очистка выводов для добавления_1 -> 1 1 + _ -> 1 _ + _ ->
Пример текста:
_1111*11111_
должен генерировать вывод:
11111111111111111111
Правила 5:
Простая машина Тьюринга ,
реализуя трехгосударственный бобр .
Лента состоит из 0s и 1s, состояния A, B, C и H (для Halt), а положение головы указывается путем записи буквы состояния перед символом, где находится голова.
Все части исходной ленты, на которой работает машина, должны быть указаны на входе.
Кроме того, демонстрируя, что алгоритм Маркова является Turing-полным, он также заставил меня поймать ошибку в реализации C ++, которая не была захвачена первыми четырьмя наборами правил.
Машина Тьюринга: бобер с тремя состояниями # состояние A, символ 0 => запись 1, перемещение вправо, новое состояние BA0 -> 1B состояние A, символ 1 => запись 1, перемещение влево, новое состояние C0A1 -> C01 1A1 -> C11 состояние B, символ 0 => запись 1, перемещение влево, новое состояние A0B0 -> A01 1B0 -> A11 состояние B, символ 1 => записать 1, двигаться вправо, новое состояние BB1 -> 1B состояние C, символ 0 => запись 1, перемещение влево, новое состояние B0C0 -> B01 1C0 -> B11 состояние C, символ 1 => запись 1, перемещение влево, halt0C1 -> H01 1C1 -> H11
Этот набор правил должен
000000A000000
в
00011H1111000