logo search
discrete_math1

44. Слова и языки, операции над ними, их свойства.

Определение.Входное слово – произвольная строка конечной длины, составленная из символов входного алфавита А. У таких автоматов одно или несколько состоя­ний заранее объявляются заключительными. Считается, что автомат распознал слово, поданное ему на вход, тогда и только тогда, когда он завершил работу над этим словом в одном из своих заключительных состояний.

Определение.Язык – множество всех слов, распознаваемых автоматом. Сам язык может быть как конечным, так и бесконечным, но в любом случае он состоит только из слов, распознаваемых соответствующим автоматом.

Определение.Суммой языковLиL´называется язык, который обозначаетсяL+L´и получается объединением множествLиL´, т.е.L+L´ =.

Определение.Произведением языковLиL´называется язык, который обозначаетсяL·L´ и получается в результате конкатенации всех возможных словwиw´, гдеwпринадлежит языкуL, аw´– языкуL´, т.е.L·L´ =.

Заметим, что язык L·L´, как правило, отличается от языкаL´·L, хотя некоторые слова могут принадлежать обоим произведениям.

Определение.Итерацией языкаLназывается язык, который обозначаетсяL* и получается в результате сложения бесконечного числа языков {Λ} +L+L2+L3+ … +Lk+ …, т.е.L* =

Итерация выражается через операции сложения и умножения языков. Из всех введенных операций над языками она единственная, которая позволяет из конечного языка получить бесконечный.

Таким образом, с помощью введенных операций сложения, умножения и итерации некоторые языки можно выражать в виде формул через более простые языки. Причем результатом сложения или умножения двух конечных языков всегда будет конечный язык, и лишь итерация позволяет из конечного языка получить бесконечный. Некоторые важные свойства операций над языками:

1. L1· (L2+L3) =L1·L2+L1·L3;

5. L·Λ=L;

2. (L1+L2) ·L3=L1·L3+L2·L3;

6. L·L* =L*·L;

3. L+L=L;

7. Λ+L·L* =L*;

4. L+L* =L*;

8. ((L1)*· (L2)*)* = (L1+L2)*.

Пустое подмножество множества А*, как и всякое другое его подмножество, тоже считается языком. Этот язык мы будем называть пустым языком и обозначать символом пустого множества . Очевидно, что для любого языкаLверны равенстваL+=LиL·=. Значит, при всех натуральных значенияхnвыполняетсяn=. Тогда из определения операции итерации получаем* =Λ++2+3+ … +n+ … =Λ.

Заметим также, что Λ* = Λ, поскольку Λn = Λ и Λ + Λ = Λ.

Определение.Пусть имеется алфавит А = {а1, а2, …, аs}. Одноэлементные языки а1, а2, …, аs, а также язык, содержащий только пустое словоΛ- элементарные языки.