Как вы классифицируете языки на обычные, контекстно-свободные и фразеологические структуры?

Question

Если вам дан язык, как вы узнаете, является ли он обычным, CF, но не обычным, или словосочетание, но не CF? Есть хороший способ решить эту проблему? Я мог бы произвольно попытаться сделать FA или PDA, но я чувствую, что есть лучший способ сделать это.

Классический пример:

L = {a ^ n b ^ n c ^ n | n> = 0}

С чего бы начать? Спасибо.

Answer 1

Вы вроде как их классифицируете. Я не знаю очень методичного подхода. Так как языки обычно являются подмножествами и надмножествами друг друга, вы оцениваете, где он вписывается в эту иерархию, и показывает, что он не может быть, скажем, обычным языком, но это может быть CFL.