Көпмағыналы грамматикалар

Түрлі шығарулардың көмегімен шынжыр пайда болған грамматикалар бар. Мысалы: грамматикаларда шынжыры екі түрлі шығару көмегімен пайда болуы мүмкін және оған екі түрлі синтаксистік ағаш сәйкес келеді.

Бұл шынжырдың бірінші шығаруы келесі түрде болады:

ал екіншісін былай алуға болады:

Келесі грамматика да түрлі синтаксистік ағашы бар түрлі шығарулар арқылы шынжыр құруға мүмкіндік береді.

Бұл грамматикалық шынжыр тудыратын екі шығаруы келесі түрде көрсетіледі:

Грамматиканың қарастырылған қасиеті көп мағыналық деп аталады. Ол келесі тәсіл арқылы анықталуы мүмкін. тілінің шынжыры егер оны шығару үшін біреуден артық синтаксистік ағаш бар болса көп мағыналы деп аталады. Егер грамматикасы көпмағыналы шынжыр тудырса, онда ол көп мағыналы деп аталады.

Көп мағыналық тек қана жасанды тілде болуы мүмкін емес. Яғни табиғи тілде де көп мағынасы бар сөйлемдер болуы мүмкін.

Мысалы: «Пальто испачкало окно» бұл сөйлемде бастауыш қайсы, толықтауыш қайсысы екені түсініксіз. Ал ағылшынның "They are flying planes" сөйлемі екі түрлі түсіндірілуі мүмкін, яғни: "Они пилотируют самолет" немесе «Это летящие самолеты". Көп мағыналық жасанды тілге өте жағымсыз қасиет болып саналады, себебі көп мағыналық шынжырдың бірнеше мағынасы бар және ол шығару ағашын бір мағына тәсілімен құруға мүмкіндік бермейді.

Бұдан келіп шығатын қағида, яғни тәжірибеде бір мағыналы грамматикаларды қолдану қажет. Қарастырылып жатқан грамматика көп мағыналы екеніне көз жеткізу үшін бұл грамматика тудыратын түрлі шығарулар көмегімен құрылуы мүмкін шынжырды табу жеткілікті. Бірақ бұл жерде туатын қиындық көп мағыналы шынжырды тауып алуда арнайы алгоритмнің жоқтығы. Бұл қағида формалды тілдер теориясында дәлелденген.

Егер және грамматикалары бір тілді тудырса, онда олар эквивалентті деп аталады.

Жалпы жағдайда екі берілген грамматика эквивалентті екенін тексеруге мүмкіндік беретін алгоритм жоқ екені дәлелденген. Бірақ көп мағыналық мәселесі жалпы түрде шешілмейді және кейбір жағдайларда, мысалы -грамматикасы үшін грамматика кестесінде грамматиканы көп мағыналы ететін ережелер түрі анықталған. Бұған келесі түрдегі ережелер мысал бола алады:

Грамматика кестесінде бұл ережелердің біреуі болсын болуы грамматиканың көп мағыналы екенін көрсетеді. Алайда бұл ереженің грамматика кестесінде болмауы грамматиканың көп мағыналы еместігіне кепілдік бере алмайды.