КПК вопрос › нужна помощь

у меня есть задача построить КПК, который распознает язык A= {a^m b^n | m > n} с ∑ = {a, b}.. я немного запутался, как это сделать.. ребята, вы можете помочь мне решить этот вопрос? Благодарность


computer-science automata
person tan keng    schedule 25.03.2011    source источник
comment
Домашнее задание? Пожалуйста, объясните, как вы пытались решить проблему и где вы застряли.   -  person Jouni K. Seppänen    schedule 25.03.2011
comment
Привет, Джуни, спасибо за ответ.. на самом деле это домашнее задание от моего учителя.. она попросила меня ответить на этот вопрос, но я не знаю, как ответить на него.. потому что она не объяснила ясно эту главу..   -  person tan keng    schedule 26.03.2011

Ответы (2)


arrow_upward
0
arrow_downward

Посмотрите на этот пример на странице Википедии для автоматов выталкивания вниз: это для языка { 0< sup>n1n | n 0 }, то есть некоторое количество нулей, за которыми следует такое же количество единиц. Это не совсем то же самое, что и ваша задача, но похоже. Можете ли вы понять описание, основанное на материалах вашего курса? Как бы вы изменили его, чтобы он распознавал нужный вам язык?

person Jouni K. Seppänen    schedule 26.03.2011
comment
Я не совсем понимаю эту главу.. @@ Преподаватель кратко объясняет. Думаю, мне нужно больше узнать о КПК. - person tan keng; 26.03.2011

arrow_upward
0
arrow_downward

Давайте не будем сразу переходить к разработке КПК для решения проблемы, а попробуем сначала разобраться в вопросе.

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

  1. ааб
  2. аааб
  3. ааа...б
  4. аааа..бб

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

Итак, теперь у нас есть вопрос.

Как убедиться, что количество a больше, чем количество b

Для строки, если мы начнем отменять a для каждой буквы "b" в строке
мы придем к следующему выводу

  1. Количество a было равно количеству b — после отмены ничего не осталось
  2. Количество Ь было больше, чем количество а — после отмены осталось несколько Ь.
  3. Количество оценок "а" превышало количество оценок "б". После отмены осталось несколько оценок "а".

Если мы попытаемся установить связь между «Вопросом» и теми пунктами выше, мы обнаружим, что строки, относящиеся к пункту № 3 выше, являются строками, приемлемыми для КПК.

Теперь давайте определим наш КПК следующим образом

P = ({q0,q1,qf}, {a,b}, δ, {a,b,Z0}, q0, Z0, {qf})

Функция перехода (δ):

δ(q0, a, Z0) = (q0,aZ0)  
δ(q0, a, a) = (q0, aa)  
δ(q0, b, a) = (q1, Λ)  
δ(q1, b, a) = (q1, Λ) 
δ(q1, Λ, a) = (qf, Z0) 
δ(q1, b, Z0) = (q2, Z0)  
δ(q1, Λ, Z0) = (q2, Z0)

Объяснение:

  1. Сначала мы храним a в стеке (состояние q0)
  2. Когда встречается первый b, мы извлекаем a из стека и меняем состояние на q1.
  3. Мы продолжаем извлекать из стека
  4. Если не осталось b для извлечения a из стека, мы меняем состояние на qf, чтобы указать принятие строки. (ПУНКТ № 3)
  5. Если осталось мало b, но нет a, который можно было бы вытащить из стека, мы меняем состояние с q1 на q2 (ловушка). (ПУНКТ № 2)
  6. Если ни a в стеке не осталось для извлечения, ни b не осталось во входной строке, мы снова меняем состояние с q1 на q2 (ловушка). (ПУНКТ № 1)
person user3276435    schedule 16.05.2015