1. Проблема останова, что мы про неё знаем?
Даны описание процедуры и её начальные входные данные, требуется определить,
завершится ли когда-либо выполнение процедуры с этими данными.
Альтернативой этому является то, что она работает всё время без остановки.
Проблема_остановки @ Википедия
1936, Тьюринг, проблема остановки неразрешима на машине Тьюринга - https://www.cs.virginia.edu/~robins/Tur … r_1936.pdf
быстрая категоризация:
- когда программа не имеет циклов (и поэтому останавливается)
- имеет тривиальные циклы (и поэтому останавливается)
- имеет нетривиальные циклы (неразрешимо)
- входит в бесконечный цикл (и поэтому не останавливается)
2. Можем ли мы глядя на грамматику определить, возможно ли построение ДКА ?
http://cs.stackexchange.com/questions/9 … e-to-a-rig
В общем случае не можем, пишет нам stackexchange:
the following (type of) function is uncomputable:
given a context-free grammar, either output an equivalent linear grammar, or output NO if the grammar represents a non-regular language.
3. Однако в частном случае можем (там же, по ссылке со stackexchange):
Chomsky proved that CFGs without self-embedding rules are regular (see this paper for a constructive proof
(the original paper is hard to find, see Harrison's book for the proof )
http://acl.ldc.upenn.edu/J/J00/J00-1003.pdf).
Отредактировано Лис (2017-03-25 14:34:18)