Презентация на тему Формальные грамматики

формальных языков — способ описания формального языка, то есть

выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

— первые задают правила, с помощью которых можно построить

любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет.

учёным Н. Хомским, формальные грамматики представляют собой средство строгого

описания естественных языков. Теория формальных грамматик составляет важный раздел математической лингвистики, в рамках которой принято подразделение на порождающие и распознающие формальные грамматики.

должно быть конечным, иначе человек не будет в состоянии

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

набранных цепочек, строение которых не подчиняется единым принципам, то

очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.

по способу задания языка. Имеются три основных таких способа

(вида грамматик):Распознающие грамматики, Порождающие грамматики, Перечисляющие грамматики.

которым на вход подается цепочка языка, а на выходе

устройство печатает «Да», если цепочка принадлежит языку, и «Нет» — в противном случае.

цепочек языков по требованию. Образно говоря, при нажатии кнопки

будет сгенерирована некоторая цепочка языка.

все цепочки языка. Очевидно, что если язык состоит из

бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

друг в друга. Можно ли, имея порождающую грамматику, построить,

скажем, перечисляющую? Ответ — да, можно. Для этого достаточно генерировать цепочки, упорядочив их, скажем по длине и порядку символов. Но превратить перечисляющую грамматику в распознающую в общем случае нельзя.

запустить процесс перечисления цепочек и ждать, напечатает ли перечисляющая

грамматика эту цепочку или нет. Если такая цепочка напечатана, то заканчиваем процесс перечисления и печатаем «Да». Если цепочка принадлежит языку, то она обязательно будет напечатана и, таким образом, распознана. Но, если цепочка не принадлежит языку, то процесс распознавания будет продолжаться бесконечно. Программа распознающей грамматики зациклится. В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих. Это следует иметь ввиду, когда сравнивают порождающие грамматики Хомского и распознающие машины Тьюринга.