Искусственный интеллект

Здесь o^Oj означает любую последовательность из идущих подряд т символов о,, за которыми следует единственный символ аТ Пример. Дана контекстно-свободная грамматика G: А = {av а2), N = {Л^,}, S, Р = {S -> Л^„ Л, -> Порождаемый язык ДО = {Й,"О2", п > 1}. Пример. Контекстно-зависимая грамматика А = {о,, о2, о3}, ^ = {TV,, 7V2, лу, 5, /> = {5 -> Nx, Nt Порождаемый язык Дб) = {a'a{a{, n > 1}. 5.9. Грамматический анализ и автоматы В предыдущем параграфе рассматривались формальные грамматики и порождение с их помощью, начиная с начального символа, языков или отдельных последовательностей, принадлежащих языкам. В этом параграфе решим обратную задачу. Дана грамматика и некоторая последовательность. Требуется определить, принадлежит ли данная последовательность языку, порождаемому данной грамматикой, или нет. Грамматика в этом случае выступает как средство распознавания последовательностей языка. Ограничимся случаем самой простой грамматики — автоматной. Для распознавания последовательностей, порождаемых автоматными грамматиками, может быть использована модель конечного автомата, рассмотренная в настоящей главе, поскольку между автоматной грамматикой и конечным автоматом имеется тесная связь. Суть этой связи состоит в том, что для любого языка, все последова-тельности которого порождаются некоторой автоматной грамматикой, может