Сдвинуть автоматы для языка

Я хочу разработать автоматические автоматы для языка

L = { a^i b^j c^k | i = j or k <= j <= 2k}

Решение, предложенное инструктором, показано на следующей диаграмме. Диаграмма КПК

Но меня беспокоит то, что он не обрабатывает строку формы, когда |2c| > |b|. То есть, когда в состоянии q8, что, если все B сложены, но ввод C еще не завершен. Этот переход здесь не захвачен.

Правильно ли мое беспокойство? Или предложенное решение - правильный КПК.


computation-theory nfa pushdown-automaton
person yogeshagr    schedule 15.03.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Помните, что j >= k, значит, |b| >= |с|.

Если все «b» во входных данных были прочитаны, то количество сложенных B больше (или равно) количеству «c», которые должны быть прочитаны во входных данных.

  • Если j = k, то он будет использовать переход от q8 к q8, пока не завершится ввод.
  • Если j = 2k, он будет считывать "c" (q8 -> q9) и вынимать две буквы B из стека (q9 -> q8), поэтому только строки с |b| = 2|с| можно принять.
  • Если j ‹ 2k, он будет использовать q8 -> q9 и q9 -> q8 до тех пор, пока количество сложенных B не станет равным количеству "c", которые должны быть прочитаны во входных данных. Затем он будет использовать q 8-> q8, пока ввод не будет завершен.
person Luciana Abud    schedule 15.03.2017
comment
Я понимаю, что вы говорите. В предлагаемом ПДА для q8 -> q8 условие перехода: (C, B-> E). Что происходит, когда |b| = 6 и |с| = 4. Строка этой формы должна быть приемлемой. Но этот КПК этим делом не занимается, верно? - person yogeshagr; 15.03.2017
comment
Оно делает. После того, как он прочитает все bs на входе, в стопке будет 6 B. Затем два cs считываются во входных данных с помощью q8 -> q9 и q9 -> q8 дважды, что берет 4 B из стека. Таким образом, у нас осталось две cs, которые нужно прочитать во входных данных, и две B, сложенные друг в друга. Затем дважды используется q8 -> q8, и строка принимается. - person Luciana Abud; 15.03.2017
comment
Хорошо, да, это так. Ваш третий пункт правильно объясняет это. На самом деле я исчерпал все B, прочитав 3 cs и сложив 6 B. Тогда у меня в стеке осталось 1 с и 0 В, и мне некуда было деваться от q8. Так имеет ли значение порядок переходов в NFA? Можем ли мы преобразовать этот КПК в программу, и тогда сможет ли компьютер принять порядок, в котором он должен делать переходы? Я имею в виду, помогает ли этот КПК написать правильную/лучшую программу? - person yogeshagr; 16.03.2017