简述正则表达式与有限自动机的等价性的证明思路 并简要说明每步要完成的基本工作或要解决的关键
自动机,思路,关键
已帮助 人
-
正确答案：正则表达式与有限自动机的等价性的证明思路为正规式的合成与分解或者说状态转换函数的合成与分解。 正则表达式一有限自动机：每步的基本工作是完成正规式的分解即分解状态转换函数增加状态图中的状态或弧。 有限自动机一正则表达式：每步的基本工作是完成正规式的合成即合成状态转换函数减少状态图中的状态或弧。
正则表达式与有限自动机的等价性的证明思路为正规式的合成与分解,或者说状态转换函数的合成与分解。正则表达式一有限自动机：每步的基本工作是完成正规式的分解,即分解状态转换函数,增加状态图中的状态或弧。有限自动机一正则表达式：每步的基本工作是完成正规式的合成,即合成状态转换函数,减少状态图中的状态或弧。