Реальное использование DFA, NFA, PDA и машин Тьюринга - PullRequest
6 голосов
/ 18 сентября 2011

Сейчас я прохожу курс по теории вычислений.Я хорошо понимаю концепции.Я могу решить проблемы.И когда я спросил своего инструктора о реальных приложениях, он сказал мне, что эти концепции, безусловно, будут полезны и необходимы при разработке компилятора.Но, по крайней мере, чтобы провести содержательное исследование, мне нужны некоторые объяснения того, как я могу использовать эти понятия в своем коде.

Например, если я хочу создать свой собственный grep.Я буду использовать строковые функции в C. Я не знаю, как использовать там регулярные выражения в кодировании.

Тот же случай применим к машинам Тьюринга.

Если я хочу добавить два числа, почему ядолжны идти по этим унарным понятиям.Аппаратная часть реализует эти концепции?

Ответы [ 2 ]

9 голосов
/ 18 сентября 2011

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

Машины Тьюринга в основном являются практическими в качестве определения компьютера.Если кто-то говорит мне о новом языке, я могу проверить, является ли он настолько мощным (не путать с простотой использования), как, скажем, C или Java, пытаясь построить на нем машину Тьюринга.

4 голосов
/ 18 сентября 2011

NFA и DFA : эти два используются в компиляторах для создания токенов из символов в исходном файле и их возврата в синтаксический анализатор грамматики.Вы можете узнать больше из руководства по UNIX lex и * 1004. *

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...