请输入您要查询的字词:

 

单词 ProductOfAutomata
释义

product of automata


One way to manufacture an automaton out of existing automata is by taking productsPlanetmathPlanetmath.

Products of Two Automata

Let A1=(S1,Σ1,δ1,I1,F1) and A2=(S2,Σ2,δ2,I2,F2) be two automata. We define the product A of A1 and A2, written A1×A2, as the quituple

(S,Σ,δ,I,F):=(S1×S2,Σ1×Σ2,δ1×δ2,I1×I2,F1×F2),

where δ is a functionMathworldPlanetmath from S×Σ to P(S1)×P(S2)P(S), given by

δ((s1,s2),(α1,α2)):=δ1(s1,α1)×δ2(s2,α2).

Since S,Σ,I,F are non-empty, A is an automaton. The automaton A can be thought of as a machine that runs automata A1 and A2 simultaneously. A pair (α1,α2) of symbols being fed into A at start state (q1,q2)I is the same as A1 reading α1 at state q1 and A2 reading α2 at state q2. The set of all possible next states for the configurationMathworldPlanetmath ((s1,s2),(α1,α2)) in A is the same as the set of all possible combinationsMathworldPlanetmathPlanetmath (t1,t2), where t1 is a next state for the configuration (s1,α1) in A1 and t2 is a next state for the configuration (s2,α2) in A2.

If A1 and A2 are FSA, so is A. In addition, if both A1 and A2 are deterministicMathworldPlanetmath, so is A, because

δ((s1,s2),(α1,α2))=(δ1(s1,α1),δ2(s2,α2)),

and I is a singleton.

As usual, δ can be extended to read words over Σ, and it is easy to see that

δ((s1,s2),(a1,a2))=δ1(s1,a1)×δ2(s2,a2),

where a1 and a2 are words over Σ1 and Σ2 respectively. A word (a1,a2) is accepted by A iff a1 is accepted by A1 and a2 is accepted by A2.

Intersection of Two Automata

Again, we assume A1 and A2 are automata specified above. Now, suppose Σ1=Σ2=Δ. Then Δ can be identified as the diagonal in Σ=Σ1×Σ2=Δ2. We are then led to an automaton

A1A2:=(S,Δ,δ,I,F),

where S,I, and F are defined previously, and δ is given by

δ((s1,s2),α)=δ1(s1,α)×δ2(s2,α).

Suppose in addition that Δ is finite. From the discussion in the previous section, it is evident that the languagePlanetmathPlanetmath accepted by A1A2 is the same as the intersectionDlmfMathworldPlanetmath of the language accepted by A1 and the language accepted by A2:

L(A1A2)=L(A1)L(A2).

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 8:20:40