Конечные автоматы как акцепторы (программирования) языка - PullRequest
Новая
       41

Конечные автоматы как акцепторы (программирования) языка

0 голосов
/ 13 января 2012

Я знаю, как 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 Ответ

4 голосов
/ 13 января 2012

Нет, это не совсем верно.Чтобы понять, как FSA связаны с вычислениями, вам нужно принять более общий взгляд на вычисления.

В общем, вычисления - это получение входных данных и получение выходных данных.А сейчас давайте сосредоточимся на одном типе проблемы, на который мы можем рассчитать ответ: решение проблем, где вывод ограничен «да» или «нет».Давайте далее ограничим виды проблем, о которых мы говорим, теми задачами решения, чьи входные данные являются строками (например, «nice»).Это именно те вопросы, на которые FSA могут быть использованы для ответа (но они не могут ответить на все из них!).

Таким образом, FSA может ответить (на некоторые) вопросы следующего вида: обладает ли строка Xсвойство Y?Примерами этого являются: «Является ли строка одной из известного конечного набора строк?», «Является ли строка двоичным представлением нечетного числа?», «Есть ли в строке« cat »в качестве подстроки?».На все эти вопросы могут ответить FSA.

Ваши проблемы, такие как 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?».Для общего ответа на этот вопрос не существует TM, т. Е. Алгоритма?»Естественно, это зависит от правил вашего языка.Строки вида «Число + Число + ... + Число» могут быть распознаны FSA, но FSA не может сказать вам, какова сумма.Тем не менее, вы не можете добавить скобки к этому, иначе FSA больше не подходят.Другими словами, существует разница между распознаванием строк и результатами вычислений, и FSA обычно считается выполнением первого.

Пожалуйста, не стесняйтесь задавать любые дополнительные вопросы.Если вас интересуют такие вопросы, пожалуйста, покажите поддержку новой информатики StackExchange, посетив следующий сайт и подтвердив:

http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=rpnXA1_2BNYzXN85c5ibxQ2

...