Допълнение на регулярен език

Имаме регулярен език L. Ще докажем, че допълнението на езика L е отново регулярен език.

Какво е допълнение

Под допълнение на езика L разбираме всички думи, които не са в езика L. Допълнението означаваме с L'. Т.е. за азбуката Σ:

$$L^{\prime }=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

Например за езика на думите, съдържащи поне един символ 1, допълнението би било езикът, който съдържа думите, които не съдържат нито един символ 1.

Метод

Методът е много прост. Имаме регулярен език L и детерминиран тотален автомат A = ⟨Q, Σ, δ, q₀, F⟩, който го приема (всеки краен автомат може да се преобразува в такъв). Автомата A', който приема L', построяваме така, че разменяме крайните и неприемащите състояния: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Това е всичко.

Пример

Нека имаме този автомат:

Автоматът, който приема допълнението на езика, би изглеждал така:

Източници

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