Марковские подстановки

Алфавитом называется любое непустое множество. Его элементы называются буквами, а любые последовательности букв — словами в данном алфавите. Допускаются пустые слова. Пустое слово будем обозначать Λ.

Если А и B — два алфавита, причем А B то алфавит В называется расширением алфавита А.

Если слово является составной частью другого слова, то оно называется подсловом.

Определение. Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (Р, Q), состоящая в следующем. В заданном слове R находят первое вхождение слова Р (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называется результатом применения марковской подстановки (Р, Q) к слову R. Если же вхождения Р в слово R нет, то считается, что марковская подстановка (Р, Q) неприменима к слову R.

Частными случаями марковских подстановок являются подстановки с пустыми словами: ( Λ, Q), (Р, Λ ), ( Λ, Λ ).

Для обозначения марковской подстановки (Р, Q) используется запись Р —> Q. Она называется формулой подстановки (Р, Q). Некоторые подстановки (Р, Q) будем называть заключительными. Для обозначения таких подстановок будем использовать запись Р —>. Q, называя ее формулой заключительной подстановки. Слово Р называется левой частью, a Q — правой частью в формуле подстановки.