Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Определение Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.




Пример Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

а) Язык типа 0 L(G)= определяется грамматикой с правилами вывода:

1) S ® aaCFD; 2) AD ® D;

3) F ® AFB | AB;4) Cb ® bC;

5) AB ® bBA;6) CB ® C;

7) Ab ® bA;8) bCD ® e.

 

б) Контекстно-зависимый язык L(G)={anbncn | n³1} определяется грамматикой с правилами вывода:

1) S ® aSBC | abc ;2) bC ® bc;

3) CB ® BC;4) cC ® cc;

5) BB ® bb.

 

в) Контекстно-свободный язык L(G)={(ab)n(cb)n | n>0 } определяется грамматикой с правилами вывода:

1) S ® aQb | accb;

2) Q ® cSc.

 

г) Регулярный язык L(G)={w^ | wÎ{a, b}+, где нет двух рядом стоящих а} определяется грамматикой с правилами вывода:

1) S ® A^ | B^;

2) A ® a | Ba;

3) B ® b | Bb | Ab.

 

4.Задача разбора

4.1. Вывод цепочек

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

ОпределениеЦепочка b Î (VTÈVN)* непосредственно выводима из цепочки в грамматике (обозначается:aÞb), если и , где , и правило вывода содержится во множестве Р.


Поделиться:

Дата добавления: 2015-08-05; просмотров: 61; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты