Начало на реферати

Класификация на формалните граматики и на езиците, породени от тях, известна като йерархия на Чомски


Класификация на формалните граматики и на езиците, породени от тях, известна като йерархия на Чомски:

  • формалната граматика Г ще наричаме граматика от

общ тип (тип 0), ако всяко нейно правило е от вида

1A2 ,1(NT)*,2(NT)*, A  N,   (NT)+;

ако Г няма аксиома в дясна част на правило, допускаме единствено съкращаващо правило S ; езиците, породени от тези граматики наричаме езици от общ тип (езици от тип 0) и тяхното множество ще бележим с ;

  • формалната граматика Г ще наричаме конктекстна или

контекстно-зависима или граматика от тип 1, ако всяко нейно правило е от вида1A2 12,1(NT)*,

2(NT)*, A  N,   (NT)+; думите1 и 2 наричаме съответно ляв и десен контекст; ако Г няма аксиома в дясна част на правило, допускаме единствено съкращаващо правило S ; езиците, породени от тези граматики наричаме контекстни (контекстно-зависими) езици (езици от тип 1) и тяхното множество ще бележим с ;

  • формалната граматика Г ще наричаме безконктекстна или

контекстно-свободна или граматика от тип 2, ако всяко нейно правило е от вида A , A  N,   (NT)+; ако Г няма аксиома в дясна част на правило, допускаме единствено съкращаващо правило S ; езиците, породени от тези граматики наричаме безконтекстни (контекстно-свободни) езици (езици от тип 2) и тяхното множество ще бележим с ;

  • формалната граматика Г ще наричаме автоматна или

граматика от тип 3, ако всяко нейно правило е в един от видовете A B, A a, A aB, a  T , A  N, B  N; ако Г няма аксиома в дясна част на правило, допускаме единствено съкращаващо правило S ; езиците, породени от тези граматики наричаме автоматни езици (езици от тип 3) и тяхното множество ще бележим с ;

описаните граматики от тип 3 се наричат още ляво-линейни, тъй като се допускат правила A aB; ако вместо това допускаме правила A Ba (но не и A aB), тогава такива граматики наричаме дясно-линейни; тъй като те в някакъв смисъл са еквивалентни, ще разглеждаме само ляво-линейни граматики;














Свойства на Автоматните езици

Нека A е азбука; въвеждаме операции в множеството от всички езици над азбуката A:

  1. нека L1  A*, L2  A*; дефинираме сума на езиците L1 и L2:

L1 + L2 = L1  L2;

  1. нека L1  A*, L2  A*; дефинираме произведение на езиците

L1 и L2: L1L2 = {  |   L1,   L2 };

дефинираме L0 = {}, L1 = L, L2 = LL, …, Ln = Ln-1L;

  1. нека L  A*; дефинираме итерация на езика L:

;

алгебрата на езиците с въведените операции се нарича

алгебра на Клини; ще отбележим някои свойства на операциите:


L1 + L2 = L2 + L1 събирането е комутативно;

(L1 + L2) + L3 = L1 + (L2 + L3) – събирането е асоциативно;

L +=+ L = L -е неутрален елемент на събирането;

(L1L2)L3 = L1(L2L3) – произведението е асоциативно;

L1L2  L2L1 в общия случай произведението не е комутативно;

L{} = {}L = L – {} е неутрален елемент на умножението;

(L1 + L2).L3 = L1.L3 + L2.L3 дясна дистрибутивност на умножението спрямо събирането;

(L1 + L2).L3 = L1.L3 + L2.L3 лява дистрибутивност на умножението спрямо събирането;


Работа на НДКА: Нека w =ai1ai2aik+1 е входна дума. По текущото състояние q на първия символ ai1 чрез d(q, ai1)={p1…pi} определяме множеството от възможни следващи състояния. По всяко от тях и по следващия входен символ ai2 чрез d се определят множествата от възможни следващи състояния и т.н. до последната буква. Ако в множеството от състоянията след нея има някое заключително състояние, казваме, че думата е разпозната. С други думи, казваме, че думата е прочетена, ако се е получило множество от вътрешни състояния, които имат с F непразно сечение.

Дефиниция: Т(А ) е езика на автомата А, т.е. Т(А)= {ÎaV*: d(q0,a)ÇFƹ}

Дефиниция: Два НДКА автомата са еквивалентни, ако Т(А1)=Т(А2).

Теорема: За всяко НДКА съществува еквивалентен на него ДКА

Така ДКА и НДКА са взаимозаменяеми. ДКА са по-лесни за употреба, макар че понякога от технически съображения се предпочитат НДКА.


Класификация на формалните граматики и на езиците, породени от тях, известна като йерархия на Чомски facebook image
Публикувано от: Снежана Иванова

Are poor people poor or just lazy? 9 out of 10 based on 2 ratings. 2 user reviews.