Какой тип языка для

Question

{xwx|x€{a,b}+,w€{a,b}+}

Это регулярно или CFG? Как я вижу, я могу написать как (a+b)(a+b)+(a+b), Так должно быть регулярно, но я не уверен.

Answer 1

Как и говорил, этот язык не может быть регулярным, так как x появляется дважды. Это язык без контекста, потому что автомат с нажатием кнопки может принять его, нажимая a и b в первом x и совать им второй x, Классическим примером для контекстно-свободных языков является язык Dyck, который состоит из строк с правильно вложенными круглыми скобками. И это также правильно, что ваши два выражения не эквивалентны.