740 views
0 votes
0 votes
Read the informal definition of the finite state transducer given in question $24.$ Give a formal definition of this model, following the pattern in Definition $1.5$ $\text{(page 35).}$ Assume that an $FST$ has an input alphabet $Σ$ and an output alphabet $Γ$ but not a set of accept states. Include a formal definition of the computation of an $FST.$ $(Hint:$ An $FST$ is a $5$-tuple. Its transition function is of the form $δ : Q×Σ→Q×Γ.)$

1 Answer

0 votes
0 votes
A finite state transducer is a 5-tuple (Q,Σ, Γ, δ, q0), where
i) Q is a finite set called the states,
ii) Σ is a finite set called the alphabet,
iii) Γ is a finite set called the output alphabet,
iv) δ : Q × Σ−→Q × Γ is the transition function,
v) q0 ∈ Q is the start state.
Let M = (Q,Σ, Γ, δ, q0) be a finite state transducer, w = w1w2 · · ·wn be a string
over Σ, and v = v1v2 · · · vn be a string over the Γ. Then M outputs v if a sequence of
states r0, r1, . . . , rn exists in Q with the following two conditions:
i) r0 = qo
ii) δ(ri, wi+1) = (ri+1, vi+1) for i = 0, . . . , n − 1.

Related questions

1 votes
1 votes
0 answers
1
0 votes
0 votes
0 answers
2
admin asked Apr 21, 2019
616 views
Using the solution you gave to question $25,$ give a formal description of the machines $T_{1}$ and $T_{2}$ depicted in question $24.$
0 votes
0 votes
0 answers
4
admin asked Apr 21, 2019
532 views
Let $B$ be any language over the alphabet $Σ.$ Prove that $B = B^{+}$ iff $BB ⊆ B.$