Как мне спроектировать функции перехода для этого автомата? - PullRequest
Новая
       19

Как мне спроектировать функции перехода для этого автомата?

2 голосов
/ 28 июня 2009

Я готовлюсь к тесту на КПК и хочу узнать, как сконструировать автомат с нажатием кнопки, который распознает следующий язык: 

L = {a^max(0,n-m)b^n a^m| n,m >=0}

Как я могу разработать функцию перехода для распознавания, если n-m больше 0?

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

Ответы [ 3 ]

2 голосов
/ 28 июня 2009

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

вот как я думаю, это будет работать: this - символы, считанные с входа, THIS - символы в стеке. символ X в нижней части стека означает, что n <= m не путайте <strong>X с Z , который является начальным символом стека и помогает определить, когда стек пуст.

возможно, есть некоторые проблемы с этим решением, но общий подход должен быть правильным.

... и удачи в тесте: -)

сначала вы читаете все символы a в начале строки и добавляете A в стек для каждого из них или нажимаете X , если есть не было а

затем вы читаете все символы b :

  • если стек пуст ( Z сверху), B сверху или X сверху, тогда вы нажимаете еще один B в стек.
  • если в стеке есть A сверху, то вы удалите его.

последний шаг - прочитать последние a символов.

  • если в стеке есть B , удалите его.
  • если в стеке X , оставьте его там
  • если стек пуст ( Z сверху), то это должен быть конец строки

другое редактирование:

извините, если вышесказанное неясно ... я попытаюсь формализовать это.

Принимаются состояния (4) и (5), начальное состояние (1). и это недетерминировано

и правила перехода:

состояние (1): прочитать первую партию a символов

  • (1) a ; Z / AZ -> (1)
  • (1) a ; A / AA -> (1)
  • (1) эпсилон; A / A -> (2)
  • (1) эпсилон; Z / Z -> (2)

состояние (2): чтение b символов

  • (2) b ; Z / BZ -> (2)
  • (2) b ; X / BX -> (2)
  • (2) b ; B / BB -> (2)
  • (2) b ; A / эпсилон -> (2)
  • (2) эпсилон; B / B -> (3)
  • (2) эпсилон; X / X -> (3)
  • (2) эпсилон; Z / Z -> (3)

состояние (3): читать последние a с

  • (3) a ; B / ничего -> (3)
  • (3) эпсилон; X / X -> (4)
  • (3) эпсилон; Z / Z -> (5)

состояние (4): завершающий a s, если m> n

  • (4) a ; X / X -> (4)

состояние (5) для принятия точной строки, когда m

(и просто чтобы быть абсолютно ясным - когда нет состояния состояния и курсор чтения не находится в конце слова, тогда слово не принимается)

Возможно, это можно сделать немного проще, если вместо символа стека использовать дополнительные состояния X , но, думаю, вы можете сделать это сами: -)

1 голос
/ 19 сентября 2009

Самый простой способ - написать грамматику для языка, а затем создать для этого КПК. Самый простой способ написать грамматику - это сначала разделить язык на основе этого «максимума», чтобы было легче увидеть, что происходит 

L = L1 \union L2
L1 = { b^n a^m | m >= n >= 0 }
L2 = { a^(n-m) b^n a^m | n >= m >= 0 }

теперь переписать L1 и L2, чтобы сделать их немного проще (j = m-n, k = n-m) 

L1 = { b^n a^n a^j | j,n >= 0 }
L2 = { a^k b^k b^m a^m | k,m >= 0 }

они превращаются в очень простые грамматики 

L1 := BA A
L2 := AB BA
AB := a AB b | \epsilon
BA := b BA a | \epsilon
A  := a A | \epsilon
L  := L1 | L2

теперь создайте из них КПК - проще всего использовать автоматизированный инструмент, но это можно сделать вручную, если вам нужно показать всю работу

0 голосов
/ 25 июля 2009

Я думаю, что язык L является контекстно-зависимым языком или языком типа 1 в иерархии Хомпского. Я могу ошибаться.

Язык L1 = { a^n b^n c^n : n >= 1 } является примером языка типа 1, и это выглядит довольно похоже. Это звучит как вопрос с подвохом для меня! Я не думаю, что есть грамматика типа 2 или без контекста или КПК, которая могла бы распознавать или генерировать L.

...