Каково использование конечных автоматов? [закрытый]

Это теоретические основы концепций, широко используемых в информатике и программировании, и их понимание поможет вам лучше понять, как их использовать (и каковы их пределы). Вы должны столкнуться с тремя основными из них, в порядке возрастания степени:

• Конечные автоматы, которые эквивалентны регулярным выражениям. Регулярные выражения широко используются в программировании для сопоставления строк и извлечения текста. Это простой метод описания набора допустимых строк с использованием основных символов, группировки и повторения. Они могут многое, но они не могут сопоставить сбалансированные наборы круглых скобок.
• Выпадающие автоматы, эквивалент контекстно-свободных грамматик. Парсеры и компиляторы текста / ввода используют их, когда не используются регулярные выражения. t достаточно мощный (и одна из вещей, которую вы узнаете при изучении конечных автоматов, - это то, что регулярные выражения делать не могут, что имеет решающее значение для понимания, когда писать регулярное выражение, а когда использовать что-то более сложное). Грамматики без контекста могут описывать «языки» (наборы допустимых строк), где достоверность в определенный момент при синтаксическом анализе строки не зависит от того, что еще было замечено.
• Машины Тьюринга, эквивалентные общему вычислению (все, что вы можете делать с компом). Некоторые вещи, которые вы узнаете, когда будете рассматривать их, позволят вам понять пределы самих вычислений. Хороший курс теории научит вас проблеме остановки, что позволит вам определить проблемы, для которых невозможно написать программу. Как только вы определили такую ​​проблему, тогда вы знаете, что нужно прекратить попытки (или усовершенствовать это до чего-то, что возможно).

Понимание теории и ограничений этих различных вычислительных механизмов позволит вам лучше понять проблемы и программы и глубже задуматься о программировании.

Это было запрос о работе, опубликованный около года назад на одном из сайтов по обмену внештатными программистами, в котором, по сути, был запрос на программу, которая решила бы проблему остановки. Несколько человек ответили предложениями, сказав, что «понимают требования» и могут «начать немедленно». Невозможно было написать программу, отвечающую требованиям. Понимание теории вычислений позволяет вам не быть тем участником торгов, который публично демонстрирует, что он действительно не разбирается в вычислениях (и не понимает)