2

我正在学习 PDA 上的测试，我想知道如何设计一个识别以下语言的下推自动机：

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

如何设计一个转换函数来识别是否n-m大于0？

如果你有一些课程材料解决了这个级别的练习，请放一个链接。

4

3 回答 3

2

您可以根据堆栈顶部的值决定从当前状态到哪里去，您可以使用堆栈上的符号来记录解析的状态。

这就是我认为这将如何工作： 这是从输入中读取的符号，这是堆栈上的符号。堆栈底部的符号X意味着 n <= m 不要将X与Z混淆，Z是堆栈的初始符号，有助于确定堆栈何时为空。

此解决方案可能存在一些问题，但总体方法应该是正确的。

...祝你考试顺利:-)

首先，您从字符串的开头读取所有a符号并将A添加到每个符号的堆栈中，或者如果没有a则压入X

然后您阅读所有b符号：

  • 如果堆栈为空（Z在顶部），B在顶部或X在顶部，则将另一个B推入堆栈。
  • 如果堆栈顶部有A，则将其删除。

最后一步是读取最终的 a符号。

  • 如果堆栈上有B，则将其删除。
  • 如果堆栈上有X，则将其保留在那里
  • 如果堆栈是空的（Z在顶部），那么这必须是字符串的结尾

另一个编辑：

抱歉，如果上述内容不清楚...我会尝试将其正式化。

接受状态是（4）和（5），起始状态是（1）。这是不确定的

和过渡规则：

state (1) : read the first batch of a symbols

  • (1) a; Z / AZ -> (1)
  • (1) a; A / AA -> (1)
  • (1) epsilon; A / A -> (2)
  • (1) epsilon; Z / Z -> (2)

state (2) : read b symbols

  • (2) b; Z / BZ -> (2)
  • (2) b; X / BX -> (2)
  • (2) b; B / BB -> (2)
  • (2) b; A / epsilon -> (2)
  • (2) epsilon; B / B -> (3)
  • (2) epsilon; X / X -> (3)
  • (2) epsilon; Z / Z -> (3)

state (3) : read the last as

  • (3) a; B / nothing -> (3)
  • (3) epsilon; X / X -> (4)
  • (3) epsilon; Z / Z -> (5)

state (4) : the trailing as if m > n

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

state (5) is for accepting the exact string when m < n

(and just to be absolutely clear -- when there is no way of a state and the reading cursor is not at the end of the word, then the word is not accepted)

This could maybe be made a bit simpler by using adidional states instead of the stack symbol X, but i guess you can do it yourself :-)

于 2009-06-28T16:06:27.770 回答
1

Easiest way is probably to write a grammar for the language and then build a PDA for that. Easiest way to write a grammar is to first split the language based on that 'max' so its easier to see what is going on

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

now rewrite L1 and L2 to make them a bit simpler ( 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 }

these turn into very simple grammars

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

now build a PDA from them -- easiest to use an automated tool, but can be done manually if you need to show all the work

于 2009-09-18T23:26:10.180 回答
0

I think that language L is a context-sensitive or type 1 language on the Chompsky hierarchy. I could be wrong.

Language L1 = { a^n b^n c^n : n >= 1 } is an example of a type 1 language., and this looks pretty similar. It sounds like a trick question to me! I don't think there is a type 2 or context-free grammar or PDA that could recognize or generate L.

于 2009-07-25T04:52:20.507 回答