Разлика на регулярни езици

Нека имаме два регулярни езика L₁, L₂. Ще докажем, че тяхната разлика L = L₁ ∖ L₂ също е регулярен език.

Идея

Всъщност няма много какво да се доказва. За разликата на две множества е в сила следното равенство:

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

където L₂′ е допълнението на езика L₂. От разделите за сечението на регулярни езици и за допълнението на регулярен език знаем, че регулярните езици са затворени относно двете операции. Това означава, че можем да построим автомат, който приема сечението на езици и допълнението на език. Тези автомати можем да използваме, за да построим автомат, който ще приема езика L₁ ∩ L₂′, а това е точно езикът L₁ ∖ L₂.

Пример

Нека имаме този автомат A₁, който приема всички думи, които съдържат четен брой единици:

и автомата A₂, който приема думите, съдържащи нечетен брой нули:

Ще построим автомат, който ще приема разликата на тези езици. Трябва ни следователно автоматът A₂′, който ще е допълнение на автомата A₂. Само разменяме крайните и неприемащите състояния:

Сега остава само да построим автомата A, който ще приема сечението на езиците L(A₁) и L(A₂′):

Източници

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools