Дескриптивная сложность языка

[FrenchCheese]

изучаю теорию автоматов, но не могу понять, что такое дескриптивная сложность языка?
и из за этого естественно не могу дальше понять дескриптивную сложность операции...
выручите пожалуйста

[Xaositect]

FrenchCheese в сообщении #389138 писал(а):

изучаю теорию автоматов, но не могу понять, что такое дескриптивная сложность языка?
и из за этого естественно не могу дальше понять дескриптивную сложность операции...
выручите пожалуйста

Дескриптивная сложность - это размер минимального описания. В теории автоматов это, соответственно, минимальное кол-во состояний автомата, распознающего этот язык.