Конечные автоматы как акцепторы (программирования) языка
Я знаю, как FSA принимает строку "nice" (как показано на странице Википедии), но как язык, который принимает FSA, может быть языком программирования?
Это так?; допустим, у меня есть алфавит A={1,2,+,-} и язык L={1+1,1+2,1-1,1-2}, тогда мой FSA выглядит следующим образом;
-->[1]--1-->[2]--+-->[3]--1-->[[5]]
| |
- 2-->[[6]]
|
v
[4]--1-->[[7]]
|
2-->[[8]]
Когда я достигаю принимающих состояний 5, 6, 7, 8, я знаю, каким должно быть значение, и поэтому я определил язык программирования???
И если я расширю его, чтобы иметь вложенные FSA, то я могу вычислить строки, как '1plus2' и 'sqrt(9)'.
Правильно ли это мышление?
1 ответ
Нет, это не совсем верно. Чтобы понять, как FSA связаны с вычислениями, вам нужно принять более общий взгляд на вычисления.
Вообще говоря, вычисления сводятся к получению ввода и получению результата. А сейчас давайте сосредоточимся на одной проблеме, на которую мы можем рассчитать ответ: решение проблем, когда вывод ограничен "да" или "нет". Давайте далее ограничим виды проблем, о которых мы говорим, теми задачами решения, чьи входные данные являются строками (например, "nice"). Это именно те вопросы, на которые FSA могут быть использованы для ответа (но они не могут ответить на все из них!).
Таким образом, ССА могут ответить на (некоторые) вопросы следующего вида: обладает ли строка X свойством Y? Примеры этого: "Является ли строка одной из известных, конечных наборов строк?", "Является ли строка двоичным представлением нечетного числа?", "Есть ли в строке" cat "в качестве подстроки?". На все это могут ответить ССА.
Ваши проблемы - как 1+1 - это не проблема решения. Вы можете решить проблему, однако, следующим образом: "Является ли моя строка вида" x+y=z ", где x, y и z - десятичные представления целых чисел X, Y и Z и X + Y = Z?" На этот вопрос, и многим нравится, нельзя ответить, используя FSA.
Существуют более сильные виды государственных машин; они не "конечны". Примерами могут служить автоматы сжатия (PDA), линейно-ограниченные автоматы (LBA) и машины Тьюринга (TM). Есть некоторые проблемы решения вида "обладает ли строка X свойством Y?" что даже машины Тьюринга, самый мощный из известных автоматов, не могут ответить. Один пример дает проблема остановки: "Учитывая, что x(y), где x - программа, а y - вход в программу, останавливается ли программа, представленная X, при пропуске ввода y?". Там нет ТМ, то есть нет алгоритма, чтобы ответить на этот вопрос в общем случае.
Можете ли вы написать FSA, который отвечает на вопрос "Является ли строка xa синтаксически допустимой строкой на этом языке, который я определяю?" Естественно, это зависит от правил вашего языка. Строки вида "Число + Число + ... + Число" могут быть распознаны FSA, но FSA не может сказать вам, какова сумма. Тем не менее, вы не можете добавить скобки к этому, иначе FSA больше не подходят. Другими словами, существует разница между распознаванием строк и результатами вычислений, и FSA обычно считается выполнением первого.
Пожалуйста, не стесняйтесь задавать любые дополнительные вопросы. Если вас интересуют такие вопросы, пожалуйста, покажите поддержку новой информатики StackExchange, посетив следующий сайт и подтвердив: