Формальные языки

Пусть А= { а, b, и т.д. все малые латинские буквы}. Введем процедуру, порождающую все возможные слова в алфавите А, сначала слова длины «1», далее – «2» и т.д. – длины «n». Полученное множество слов обозначается как А^* («*» – знак операции итерации).Понятно, что А^* есть бесконечное множество слов. Процедура порождения слов описывается индуктивной схемой с единственной операцией, которая называется «конкатенация» (приписывание) и обозначается «·».

1°. Вводится пустое слово –Æ(А ⁰ = Æ)

2°. К пустому слову приписываются последовательно все буквы из алфавита А, получается слово длины «1», которые составляют множество А^’= { a, b,… }.

(n-1)°. Пусть порождено множество слов длины «n – 1 » – А^{n— 1}

n°. Каждое слово y Î Aⁿ получается из x Î A^{n– 1} приписыванием букв из алфавита, так что и т.д.

Формальным языком L называется любое подмножество A *, т.е. L Í A, таким образом язык L является отношением на А *.

Пример 1.6. Задан двухбуквенный алфавит А = { a,b }. А^* – множество слов, состоящих из двух букв, приписанных в произвольном порядке. Например множество всех слов длины «2» – А² = { aa, bb, ab, ba }, A³ = { aaa, aab,bba, bbb, aba, abb baa, bab } и т.д. для любого «n». Определим несколько примеров языков.

а) Язык L ₁ = { aab, aabb } – состоит из двух слов (конечный язык).

б) Язык L ₂ = aⁿb^m; n = 1, 2, …, m = 1,2,…. Слово , а слово bab Ï L ₂.

в) Язык L ₃ = aⁿbⁿ; n = 1, 2, … содержит все слова, которые имеют одинаковое число букв а и b, например, aaabbbÎL ₃, aaaabbbb Î L ₃, а слова abab Ï L ₃, bbaa Ï L ₃.

г) Язык L ₄ = x × x ^–1 – так называемый «зеркальный» язык, где x Î A *.

Слова abba Î L ₄, baaaab Î L ₄, а слова aba Ï L ₄, aaa Ï L ₄.

Из определения формального языка вытекает, что любой язык L суть некоторое n – арное отношение на А^*, где n = 1, 2, ….