Асоціативні вирахування

Кодування і нумерація

Алфавіти і слова

Означення 1. Будемо називати довільну кінцеву множину алфавітом А, а елементи цієї множини буквами алфавіту А. Тоді довільні кінцеві послідовності букв називаються словами в даному алфавіті.

Любою алфавіт містить порожній символ. Будемо позначати його символом (. Порожній символ є і порожнім словом.

Безліч слів алфавіту А будемо позначати А*.

Визначення 2. 1. Кількість букв у слові називається його довжиною і позначається вертикальними дужками. Наприклад, довжина слова аааа дорівнює | аааа | = 4, довжина порожнього слова | L | = 0.

Основною операцією над словами є конкатенація.

Визначення 3. 2. Конкатенацією двох слів P і Q назвемо слово, отримане дописуванням слова Q після P: PQ.

Наприклад, конкатенація слів aab і ba є слово aabba. Операція конкатенації некоммутативна, але ассоциативна.

Визначення 4. 3. Якщо x - деяке слово алфавіту A і якщо x представимо у виді конкатенації PQ, те P і Q називають подсловами слова x.

Наприклад, слово abb містить подслова a, b, ab, bb. Якщо x Î A * і x = P ₁ QP ₂ QP ₃, то говорять про першому, другому і т.д. входження слова Q у слово x. Слова, складені з послідовності однакових букв, будемо іноді записувати аааbb = a ³ b ², де ступінь позначає кількість входжень букви в слово.

Визначення 5. 4. Нехай дані два алфавіти A і B. Кодування слів алфавіту A словами в алфавіті B є функція j (p), що здійснює відображення безлічі слів в алфавіті А в безліч слів в алфавіті В: j (p): A*® У *, де p Î А *, j (p) Î B *.

Якщо кожному слову в алфавіті А відповідає слово в алфавіті В, то відображення однозначне.

Приклад. Нехай A = { a, b }, B = { a, b, c }. Відображення j (p): p ® cpc визначає кодування слів в алфавіті A словами в алфавіті B, наприклад, ab ® cabc.

Визначення 6. 5. Кодування називається блоковим, якщо кожній букві алфавіту А відповідає слово в алфавіті В.

Приклад. Відображення j (a): a ® ac, j (b): b ® bc є блоковим кодуванням. Наприклад, j (ab) = acbc.

Будь-які безлічі слів у деякому алфавіті можна упорядкувати в лексикографічному порядку: якщо R ₁ aR ₂, R ₁ bR ₂ і a<b, те R ₁ aR ₂ < R ₁ bR _2..

Приклад лексикографічного упорядкування для слів алфавіту A = { a, b }:

L, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, і т.д.

Визначення 7. 6. Підстановка слова P замість Q у слові W означає заміну Q на P у слові W. Підстановка позначається: P ® Q.

Приклад. Нехай даний алфавіт А = { a, b } і підстановка ab ® ba. Тоді результат виконання підстановки над словом ababbbab буде наступним:

1. ab abbbab 2. ba ab bbab 3. b ab abbab 4. bba ab bab

5. bb ab abab 6. bbba ab ab 7. bbb ab aab 8. bbbbaa ab

9. bbbba ab a 10. bbbb ab aa 11. bbbbbaaa

Визначення 8. 7. Сукупність усіх слів алфавіту A разом з кінцевою системою припустимих підстановок називається асоціативним вирахуванням.

Дата добавления: 2014-01-07