Конструирайте граматика на следния език {a^n b^m | n,m = 0,1,2,,n ‹= 2m} [затворено]

Как се пише граматика за формален език?

Преди да прочетете този отговор, първо трябва да прочетете: Съвети за създаване Граматики без контекст.

Граматика за {aⁿ b^m | n,m = 0,1,2,..., n ‹= 2m }

Какъв е вашият език L = {aⁿ b^m | n,m = 0,1,2,..., n ‹= 2m } описание?

Описание на език: Езикът L се състои от набор от всички низове, в които символите a последвани от символи b, където броят на символа b е по-голям или равен на половината от броя на a.

За да разберете по-ясно:

В модел aⁿ b^m, първите символи a идват след това символ b. общият брой на a е n, а броят на b е m. Уравнението на неравенството казва за връзката между n и m. За да разберете уравнението:

given:   n <= 2m   
=>       n/2 <= m       means `m` should be = or > then n/2

=>       numberOf(b) >= numberOf(a)/2    ...eq-1

Така че неравенството на n и m казва:

numberOf(b) трябва да бъде повече или равно на на половината от numberOf(a)

Някои примерни низове в L:

b   numberOf(a)=0 and numberOf(b)=1  this satisfy eq-1        
bb  numberOf(a)=0 and numberOf(b)=2  this satisfy eq-1 

Така че в езиковия низ произволен брой b са възможни без a. (всеки низ от b), защото всяко число е по-голямо от нула (0/2 = 0).

Други примери:

                                     m   n
                                 --------------  
ab     numberOf(a)=1 and numberOf(b)=1 > 1/2   
abb    numberOf(a)=1 and numberOf(b)=2 > 1/2  
abbb   numberOf(a)=1 and numberOf(b)=3 > 1/2  
aabb   numberOf(a)=2 and numberOf(b)=2 > 2/2 = 1  
aaabb  numberOf(a)=3 and numberOf(b)=2 > 3/2 = 1.5
aaaabb numberOf(a)=4 and numberOf(b)=2 = 4/2 = 2  

Точки за отбелязване:

• всички горни низове са възможни, защото броят на b е или равен (=) на половината от броя на a или повече (>) .

• и интересен момент за отбелязване е, че общият брой a също може да бъде повече от броя на b, но не твърде много. Докато броят на b може да бъде повече от броя на a произволен брой пъти.

Два по-важни случая са:

• само a като низ не е възможно.

• бележка: null ^ низ също е разрешен, защото в ^ , numberOf(a) = numberOf(b) = 0, които отговарят на уравнението.

_{Веднага изглежда, че писането на граматика е трудно, но наистина не...}

Според описанието на езика се нуждаем от следните видове правила:

Правило 1: За генериране на ^ нулев низ.

 N --> ^  

Правило 2: За генериране на произволен брой от b

 B --> bB | b  

Правило 3: за генериране на a:
(1) Не забравяйте, че не можете да генерирате твърде много a, без да генерирате < em>b.
(2) Тъй като b са повече от = половината от a; трябва да генерирате един b за всяка алтернатива a
(3) Само a като низ не е възможно, така че за първата (нечетна) алтернатива трябва да добавите b с a
(4), докато за четната алтернатива можете да отхвърлите, за да добавите b ( но не е задължително)

Така че общата ви граматика:

   S --> ^ | A | B
   B --> bB | b

   A --> aCB | aAB | ^
   C --> aA | ^

тук S е начална променлива.

В горните граматични правила може да имате объркване в A --> aCB | aAB | ^, така че по-долу е моето обяснение:

A --> aCB | aAB | ^   
       ^_____^
       for second alternative a 

C --> aA    <== to discard `b`    

and  aAB  to keep b

нека генерираме някои низове в езика, използвайки тези граматични правила, пиша най-лявата деривация, за да избегна обяснение.

  ab     S --> A --> aCB --> aB --> ab                        
  abb    S --> A --> aCB --> aB --> abB --> abb
  abbb   S --> A --> aCB --> aB --> abB --> abB --> abbB --> abbb 
  aabb   S --> A --> aAB --> aaABB --> aaBB --> aabB --> aabb
  aaabb  S --> A --> aCB --> aaAB -->  aaaABB --> aaaBB --> aaabB --> aaabb
  aaaabb S --> A --> aCB --> aaAB --> aaaCBB --> aaaaABB --> aaaaBB 
                                                         --> aaaabB 
                                                         --> aaaabb

Още един за низ нечлен:

според езика a⁵ b² = aaaaabb е не възможно. защото 2 >= 5/2 = 2,5 ==> 2 >= 2,5 неравенството е неуспешно. Така че не можем да генерираме този низ и с помощта на граматиката. Опитвам се да покажа по-долу:

В нашата граматика, за да генерираме допълнителни a, трябва да използваме C променлива.

S --> A 
  --> aCB 
  --> aaAB 
  --> aa aCB B 
  --> aaa aA BB 
  --> aaaa aCB BB  
           ---              
            ^
           here with firth `a` I have to put a `b` too

Докато отговорът ми е готов, но мисля, че можете да промените правилата на A като:

A --> aCB | A | ^

Пробвам!!

РЕДАКТИРАНЕ:
_{както @us2012 коментира: Струва ми се, че тогава S -> ^ | ab | aaSb | Sb би било по-просто описание. Чувствам, че този въпрос би бил добър за OP и други също.}

Език на ОП:

L = {aⁿ b^m | n,m = 0,1,2,..., n ‹= 2m}.

Граматиката на @us2012:

S -> ^ | ab | aaSb | Sb    

Въпрос на @us2012:

Дали тази граматика също генерира език L?

Отговорът е Да!

Неравенството в езика между броя на a = n и броя на b = m е n =< 2m

Можем да разбираме и като:

 n =< 2m

 that is 

 numberOf(a) = <  twice of numberOf(b) 

И в граматиката, дори когато добавим един или две a, ние също добавяме един b. Така че в крайна сметка броят на a не може да бъде повече от два пъти по-голям от броя на b.

Граматиката също има правила за генериране. произволни числа на b и null ^ низове.

Така че опростената граматика, предоставена от @us2012, е ПРАВИЛНА и също генерира точно език L.

Забележка: Първото решение дойде от деривация, тъй като написах в свързан отговор, започнах с описание на езика, след което се опитах да напиша някои основни правила и постепенно успях да напиша пълна граматика.

Докато отговорът на @us2012 идва от способността, вие можете да придобиете способността да пишете граматика, като прочетете други решения и напишете вашето за същото...като учите програмиране.