-4
{xwx|x€{a,b}+,w€{a,b}+}
Является ли он регулярным или CFG? Как я вижу, я могу написать его как (a+b)(a+b)+(a+b). Так что это должно быть регулярно, но я не уверен.Что такое тип языка для
A
ответ
1
Как и тыквы, этот язык не может быть регулярным, так как x появляется дважды. Это контекстно-свободный язык, потому что автомат pushdown может принять его, нажав a и b в первом x и вытащив его на второй x. Классическим примером для контекстно-свободных языков является Dyck language, который состоит из строк с правильно вложенными круглыми скобками. И также правильно, что ваши два выражения не эквивалентны.
«x» то же самое в начале и в конце, поэтому ваше выражение не эквивалентно, так как оно не запоминает первый «x». Это не регулярно. – poke