Докажите, что дополнение к

12

Я хочу доказать, что дополнение не является регулярным, используя свойства замыкания.{0N1N|N0}

Я понимаю, что лемму прокачки можно использовать, чтобы доказать, что не является регулярным языком. Я также понимаю, что обычные языки закрыты в рамках операции дополнения. Однако означает ли это, что дополнение к нерегулярному языку также является нерегулярным?{0N1N|N0}

anthony34234
источник

Ответы:

9

Да. Поскольку дополнение регулярного языка также является обычным языком, из этого следует, что дополнение к нерегулярному языку также должно быть нерегулярным. Строго говоря, это работает, поскольку дополнение является его собственным обратным.

Patrick87
источник
3
{0N1N|N0}