Создайте грамматику, используя следующий язык {a^n b^m | n,m = 0,1,2,...,n <= 2m}

Я просто взял свой промежуточный курс, но не смог ответить на этот вопрос.

Может кто-нибудь дать пару примеров языка и построить грамматику для языка или хотя бы показать мне, как я это сделаю?

Также, как написать грамматику для L:

L = {an bm | n, m = 0,1,2,..., n <= 2m}?

Заранее спасибо.

Источник

1 ответ

Решение

Как написать грамматику для формального языка?

Прежде чем читать мой ответ, вы должны сначала прочитать: Советы по созданию контекстно-свободных грамматик.

Грамматика для {a n b m | n, m = 0,1,2,..., n <= 2m}

Какой у вас язык L = {a n b m | n, m = 0,1,2,..., n <= 2m} описание?

Описание языка: язык L состоит из набора всех строк, в которых символы a следуют символы b где номер символа b больше или равно половине числа a "S.

Чтобы понять более четко:

В шаблоне a n 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 говорит:

число Of (b) должно быть больше или равно половине числа Of (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 "S. (любая строка из 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 "S:
(1) Помните, что вы не можете создать слишком много a без генерации b "S.
(2) потому что b более чем на половину a "S; вам нужно сгенерировать один 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 5 b 2 = 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 n b m | n, m = 0,1,2,..., n <= 2m}.

грамматика @us2012:

S -> ^ | ab | aaSb | Sb

@us2012 вопрос:

Эта ли грамматика также порождает язык L?

Ответ - да!

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

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

 n =< 2m

 that is 

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

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

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

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

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

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

Источник
Другие вопросы по тегам