Проверка свойств языка

Question

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

они заключаются в следующем:

A ^ (B ^ C) = (A ^ B) ^ C (который я считаю ассоциативным правилом)

A ^ (BUC) = (A ^ B) U (A ^ C) (правило распределения)

В этих примерах я использовал ^ для обозначения конкатенации

Answer 1

First

A ^ B - это все слова x, такие что v в A и w в B такие, что x = vw

давайте докажем, что A ^ (B ^ C) входит в (A ^ B) ^ C

A ^ (B ^ C) - это все слова x, такие что v в A и w в B ^ C такой что x = vw

и w = lm, где l в B и m в C, тогда x = vlm

x = (vl) m = v (lm), поскольку vl находится в A ^ B, а m находится в C, тогда x находится в (A ^ B) ^ C.

затем A ^ (B ^ C) включается в (A ^ B) ^ C.

То же доказательство для обратного включения

затем A ^ (B ^ C) = (A ^ B) ^ C

Второй:

x в B U C тогда и только тогда, когда x находится в B или x в C.

первое включение:

если x в A ^ (B U C)

тогда x = vw, где v в A и w в B или C

Тогда x находится в A ^ B или A ^ C

, затем x находится в (A ^ B) U (A ^ C)

второе включение

, если x в (A ^ B) U (A ^ C)

тогда x = vw с v в A и w в B или x = vw с v в A и w в C

тогда, поскольку v всегда есть A

, тогда x = vw, где v в A и w в B или C

x в A ^ (B U C)

Следовательно A ^ (B U C) = (A ^ B) U ( A ^ C)