-2

http://i.stack.imgur.com/QoXru.png

a) 构造 M 的转移表 b) 字符串 baba,baab,abab,abaaab c) 给出 L(M) 的正则表达式

我实际上是因为生病而缺课的那天,我对此感到非常困惑。我查看了维基百科有关 DFA 的信息,但这让我更加困惑。任何与此问题相关的主题的见解将不胜感激!

4

1 回答 1

0

DFA = 确定性有限状态自动机(搜索),

  • 有一个开始状态(见q0,>旁边的),
  • (零个或多个)由圆圈指定的非终止状态(见里面的名称),
  • 由双同心圆表示的终端(结束)状态,
  • 由线(箭头)指定的状态转换,由事件标记

DFA (DFSA) 可用于“识别”输入模式。您将输入模式(字符串)提供给 DFA,当 DFA 在状态之间转换时,它要么识别下一个条目,要么产生错误/无法识别的结果。输入完成后,检查结束状态是否为终端/已识别状态。

实现如下:

states[] = { 'q0', 'q1', 'q2' }
events[] = { 'a', 'b' }
transition[]
transition['q0'] = []
transition['q1'] = []
transition['q2'] = []
transition['q0']['a'] = 'q1'
transition['q0']['b'] = 'q0'
transition['q1']['a'] = 'q1
transition['q1']['b'] = 'q2'
transition['q2']['a'] = 'q0'
transition['q2']['b'] = 'q1'
state = 'q0' #start state
terminal[]
terminal['q2'] = true # you can have more than one terminal/recognized state
terminal['q0'] = false # you can have more than one terminal/recognized state
terminal['q1'] = false # you can have more than one terminal/recognized state

您可以将上述状态机实现为, (rubylike) terminal['q2'] = 1 # 您可以拥有多个终端/已识别状态

def DFArun( initstate, input )
    state = initstate
    each input.each do |inp|
        if !transition[ state, inp ].exists then
            return :notrecognized
        end
        state = transition [ state, inp ]
    end
    if terminal[ state ].exists then return :recognized
    else return :notrecognized end
end

您可以使用进行某些转换时发生的语义操作进一步注释 DFSA 或 DFSM(确定性有限状态机)。这可以是在某些转换(“已识别”)上“发出”输出,或导致某些动作发生。DFA(DFSA、DFSM)可用于识别语言解析器中的标记,或控制工厂自动化或业务工作流程。

您可以轻松地在文件中表达对 DFSM 的识别,该文件可以加载到 DFSM 中进行操作,从而构建其动作由可编辑文件控制的程序。例如,一个简单的 CSV 文件,

#state,input,newstate,actions(optional)
q0,a,q1,none
q0,b,q0,none
q1,a,q1,none
q1,b,q2,none
q2,a,q0,none
q2,b,q1,none
init,q0
terminal,q2
于 2013-10-23T23:25:55.047 回答