Постройте грамматику для следующего языка {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 в виде строки невозможно.

• Примечание: нулевая строка ^ также разрешена, потому что в ^ , 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

Еще один для строки non-member:

согласно языку 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 | ^

Попробуйте!

EDIT:
_{как прокомментировал @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's = n и количеством b = m составляет n =< 2m

Мы также можем понимать как:

 n =< 2m

 that is 

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

И в грамматике, даже когда мы добавляем один или два a, мы также добавляем один b . Таким образом, в конечном итоге количество a не может быть более чем в два раза больше количества b.

Грамматика также имеет правила для генерации. любое количество строк b и пустых строк ^.

Таким образом, упрощенная грамматика, предоставленная @us2012, является ПРАВИЛЬНОЙ и также точно генерирует язык L.

Примечание: Первое решение пришло из вывода, как я написал в связанном ответе, я начал с описания языка, затем попытался написать некоторые основные правила, и постепенно я мог написать полную грамматику.

В то время как ответ @ us2012 пришел благодаря способностям, вы можете получить способность писать грамматику, читая чужое решение и записывая свое для того же ... как вы изучаете программирование.