这种确定性有限自动机的语言是什么? [英] What is the language of this deterministic finite automata?

问题描述

给出:

我不知道接受的语言是什么.

I have no idea what the accepted language is.

通过查看它，您可以获得几个最终结果:

From looking at it you can get several end results:

1.) bb
2.) ab(a,b)
3.) bbab(a, b)
4.) bbaaa

推荐答案

如何为DFA编写正则表达式

在任何自动机中，状态的目的就像存储元素.状态会自动存储一些信息，例如风扇开关.
一种确定性有限自动机(DFA)，称为 finite 自动机，因为有限数量的内存以状态形式存在.对于任何常规语言(RL)，始终可以使用DFA.

How to write regular expression for a DFA

In any automata, the purpose of state is like memory element. A state stores some information in automate like ON-OFF fan switch.
A Deterministic-Finite-Automata(DFA) called finite automata because finite amount of memory present in the form of states. For any Regular Language(RL) a DFA is always possible.

让我们看看DFA中存储了哪些信息(请参阅我的彩色图).
(注意:在我的解释中，任何数字表示零次或多次，并且Λ为空符号)

Let's see what information stored in the DFA (refer my colorful figure).
(note: In my explanation any number means zero or more times and Λ is null symbol)

状态1:是START状态，存储在其中的信息是偶数 a .还有零 b.
此状态的正则表达式(RE)为 = (aa)*.

State-1: is START state and information stored in it is even number of a has been come. And ZERO b.
Regular Expression(RE) for this state is = (aa)*.

状态4:已出现奇数个 a .还有零 b .
此状态的正则表达式为 = (aa)*a.

State-4: Odd number of a has been come. And ZERO b.
Regular Expression for this state is = (aa)*a.

图:一个 BLUE 状态= 偶数 a 和 RED 状态= ODD a 的数量已经到来.

Figure: a BLUE states = EVEN number of a, and RED states = ODD number of a has been come.

注意::一旦出现第一个 b ，就不能再回到状态1和状态4.

NOTICE: Once first b has been come, move can't back to state-1 and state-4.

状态5:位于Yellow b之后. Yellow b 是指 b after odd numbers of a.
在奇数个 a 之后(在状态5)，一旦您获得 b ，每件事都是可以接受的，因为在(b，a)处存在一个自循环状态5.

State-5: comes after Yellow b. Yellow b means b after odd numbers of a.
Once you gets b after odd numbers of a(at state-5) every thing is acceptable because there is self a loop for (b,a) at state-5.

您可以写为状态5:黄色-b，后跟 = Yellow-b (a + b)*

You can write for state-5 : Yellow-b followed-by any string of a, b that is = Yellow-b (a + b)*

状态6::仅用于区分是奇数 a 还是偶数.

State-6: Just to differentiate whether odd a or even.

状态2 :先后依次是 a 和 b ，然后是任意数量的 b . = (aa)* bb*

State-2: comes after even a then b then any number of b. = (aa)* bb*

状态3:在状态2之后，然后是第一个a，然后是通过状态6的循环. 我们可以为状态3来写 = state-2 a (aa)* = (aa)*bb* a (aa)*

State-3: comes after state-2 then first a then there is a loop via state-6. We can write for state-3 comes = state-2 a (aa)* = (aa)*bb* a (aa)*

因为在我们的DFA中，我们有三个最终状态，所以DFA接受的语言是三个RL(或三个RE)的并集(RE中的+).
因此，DFA接受的语言对应于三个接受状态的 states-2,3,5 ，我们可以这样写:

Because in our DFA, we have three final states so language accepted by DFA is union (+ in RE) of three RL (or three RE).
So the language accepted by the DFA is corresponding to three accepting states-2,3,5, And we can write like:

 State-2 +  state-3           + state-5    

(aa)*bb* + (aa)*bb* a (aa)* + Yellow-b (a + b)*

(aa)*bb* + (aa)*bb* a (aa)* + Yellow-b (a + b)*

我忘了解释how Yellow-b comes?
解答:Yellow-b是状态4或状态3之后的b.我们可以这样写:

I forgot to explain how Yellow-b comes?
ANSWER: Yellow-b is a b after state-4 or state-3. And we can write like:

Yellow-b = ( state-4 + state-3 ) b = ((aa)*a + (aa)*bb* a (aa)*)b

Yellow-b = ( state-4 + state-3 ) b = ( (aa)*a + (aa)*bb* a (aa)* ) b

[ ANSWER ]
(aa)*bb* + (aa)*bb* a (aa)* +((aa)*a + (aa)*bb* a (aa)*)b (a + b)*

[ANSWER]
(aa)*bb* + (aa)*bb* a (aa)* + ( (aa)*a + (aa)*bb* a (aa)* ) b (a + b)*

语言的英语描述:DFA接受三种语言的组合

English Description of Language: DFA accepts union of three languages

• a 的数量，后跟一个或多个 b 的
• 偶数个 a ，接着一个或多个 b ，奇数个 a 的.
• a 和 b 的前缀字符串，奇数个 a ，后跟 b ，后跟任何字符串 a 和 b 和 Λ .

• EVEN NUMBERs OF a's, FOLLOWED BY ONE OR MORE b's,
• EVEN NUMBERs OF a's, FOLLOWED BY ONE OR MORE b's, FOLLOWED BY ODD NUMBERs OF a's.
• A PREFIX STRING OF a AND b WITH ODD NUMBER OF a's, FOLLOWED BY b, FOLLOWED BY ANY STRING OF a AND b AND Λ.

英语描述很复杂，但这是描述语言的唯一方法.您可以通过先将给定的DFA转换为最小化的DFA，然后编写RE和说明来进行改进.

English Description is complex but this the only way to describe the language. You can improve it by first convert given DFA into minimized DFA then write RE and description.

此外，还有一种衍生方法可使用如何使用Arden定理为DFA编写正则表达式.首先必须将过渡图转换为没有零移动和单启动状态的标准形式.但是我更喜欢通过分析学习计算理论，而不是使用数学推导方法.

Also, there is a Derivative Method to find RE from a given Transition Graph using Arden's Theorem. I have explained here how to write a regular expression for a DFA using Arden's theorem. The transition graph must first be converted into a standard form without the null-move and single start state. But I prefer to learn Theory of computation by analysis instead of using the Mathematical derivation approach.

这篇关于这种确定性有限自动机的语言是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！