Lab Session #3 #

Agenda #

• Finite State Transducers
• Exercises on Finite State Transducer

Finite State Transducer #

A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA.

An FSA defines a formal language by defining a set of accepted strings, while an FST defines relations between sets of strings. An FST will read a set of strings on the input tape and generates a set of relations on the output tape. An FST can be thought of as a translator or relater between strings in a set. In morphological parsing, an example would be inputting a string of letters into the FST, the FST would then output a string of morphemes.

FSTs are used in a variety of applications, including:

Natural language processing: FSTs are used in natural language processing for tasks such as morphological analysis, part-of-speech tagging, and named entity recognition. Speech recognition: FSTs are used in speech recognition for tasks such as acoustic modeling and decoding. Machine translation: FSTs are used in machine translation for tasks such as lexical translation and grammar conversion. Compilers: FSTs are used in compilers for tasks such as lexical analysis and syntax analysis. FSTs are a powerful tool for modeling and manipulating strings. They are used in a variety of applications, including natural language processing, speech recognition, machine translation, and compilers.

Finite State Transducer formula #

A finite state transducer (FST) is a tuple \( \langle \) \(Q\) , \(I\) , \(\delta\) , \(q_0\) , \(F\) , \(O\) , \(\eta\) \(\rangle\) , where:

• \(Q\) is a finite set of states. Each state represents a possible configuration of the FST.
• \(I\) is a finite input alphabet. Each symbol in the input alphabet represents a possible input that the FST can read.
• \(\delta\) is the transition function. It maps a state and an input symbol to a new state.
• \(q_0\) is the initial state. This is the state that the FST starts in when it is first activated.
• \(F\) is the set of final states. A state is a final state if it represents a valid output.
• \(O\) is the output alphabet. Each symbol in the output alphabet represents a possible output that the FST can produce.
• \(\eta\) is the output function. It maps a state and an input symbol to a sequence of output symbols. The rule that all of these variables follow is that they must be finite. This means that there can only be a finite number of states, input symbols, final states, and output symbols. This is because an FST is a finite-state machine, which is a machine that can only be in a finite number of states at any given time.

Remark

• the condition for acceptance remains the same as in acceptors
• the translation is performed only on accepted strings

Example #

Build a complete FST accepting the following language over the alphabet \( A = \{0,1 \}\) .
\[ L = \{ x \isin A^* | \textit { the number of } 0's \textit{ is even} \} \]

The FST outputs the string obtained by removing every odd occurrence of 0 and doubling every occurrence of 1. Examples of inputs recognised by L and their respective outputs:

• Input: \(010010\) , Output: \( 110110\)
• Input: \(00\) , Output: \(0\)
• Input: \(000100011\) , Output: \(011001111\)

Solution ▾

Exercises #

Build complete FSAs over the languages given below:

1. \( A = \{w,t,a,l,k,e,d\} \) that accepts only the verb ”walked” or ”talked”. The FST will translate the input verb to present form ex: walked to walk.
   Solution ▾

   
2. \(A = \{a, b\} \) that accepts only strings ending with the letter b. The FST will translate the input string where every second symbol a in the input is erased.
   Solution ▾

   
3. \(A = \{0, 1\} \) that accepts strings that are binary representation of integers divisible by 2. The FST will translate the input string into result of division by 2.
   Solution ▾

   
4. \(A = \{0, 1\} \) that accepts strings that are binary representation of integers divisible by 3. The FST will translate the input string into result of division by 3.
   Solution ▾

   

Operations on FSA #

Intersection #

Intersection Formula #

Suppose \( M_1 = \lparen Q_1, A, \delta_1, q^1_0, F_1 \rparen \) and \( M_2 = \lparen Q_2, A, \delta_2, q^2_0, F_2 \rparen\) are finite state automata accepting \( L_1 \) and \(L_2 \) , respectively. Let \( M \) be the complete \( \text {FSA M} = \lparen Q,A,\delta,q_0,F \rparen \) ,
where:

\[ Q = Q_1 \times Q_2 \] \[ q_0 = \lparen q^1_0, q^2_0 \rparen \] the transition function \( \delta\) is defined by the formula \[ \delta \lparen \lparen q, p \rparen, a \rparen = \lparen \delta_1 \lparen q, a \rparen , \delta_2 \lparen p, a \rparen \rparen \] for every \( q \isin Q_1 \) , every \( p \isin Q_2 \) , and every \( a \isin A \) . And the set of the final states is defined as: \[ F= \lbrace \lparen q,p \rparen | q \isin F_1 \land p \isin F_2 \rbrace \] \( M \) accepts the language \( L_1 \cap L_2 \) .

Intersection Example #

Let \( M_1\) be a complete \(\text{FSA}\) defined as

• \( \lbrace q_0, q_1 \rbrace \rarr\) set of states;

• \( \lbrace a \rbrace \rarr \) input alphabet;

• \( \lbrace \lparen \lparen q_0,a \rparen, q_1 \rparen, \lparen q_1,a \rparen, q_0 \rparen \rbrace \rarr \) partial transition function;

• \( q_0 \rarr \) initial state;

• \( \lbrace q_1 \rbrace \rarr \) set of final states;

Let \( M_2\) be a complete \(\text{FSA}\) defined as

Then :

\[ \lparen M_1 \cap M_2 \rparen = \lang \lbrace \lparen q_0, p_0 \rparen , \lparen q_1, p_0 \rparen \rbrace, \lbrace a \rbrace, \lbrace \lparen \lparen \lparen q_0, p_0 \rparen, a \rparen , \lparen q_1, p_0 \rparen \rparen , \] \[\lparen \lparen \lparen q_1, p_0 \rparen ,a \rparen , \lparen q_0,p_0 \rparen \rparen \rbrace , \lparen q_0, p_0 \rparen ,\lbrace \lparen q_1, p_0 \rparen \rbrace \rang .\]

Intersection Graph #

Union #

Suppose \( M_1 = \lparen Q_1, A, \delta_1, q^1_0, F_1 \rparen \) and \( M_2 = \lparen Q_2, A, \delta_2, q^2_0, F_2 \rparen\) are finite state automata accepting \( L_1 \) and \(L_2 \) , respectively. Let \( M \) be the complete \( \text {FSA M} = \lparen Q,A,\delta,q_0,F \rparen \) ,
where:

\[ Q = Q_1 \times Q_2 \] \[ q_0 = \lparen q^1_0, q^2_0 \rparen \] the transition function \( \delta\) is defined by the formula \[ \delta \lparen \lparen q, p \rparen, a \rparen = \lparen \delta_1 \lparen q, a \rparen , \delta_2 \lparen p, a \rparen \rparen \] for every \( q \isin Q_1 \) , every \( p \isin Q_2 \) , and every \( a \isin A \) . And the set of the final states is defined as: \[ F= \lbrace \lparen q,p \rparen | q \isin F_1 \lor p \isin F_2 \rbrace \] \( M \) accepts the language \( L_1 \cup L_2 \) .

Difference #

Suppose \( M_1 = \lparen Q_1, A, \delta_1, q^1_0, F_1 \rparen \) and \( M_2 = \lparen Q_2, A, \delta_2, q^2_0, F_2 \rparen\) are finite state automata accepting \( L_1 \) and \(L_2 \) , respectively. Let \( M \) be the complete \( \text {FSA M} = \lparen Q,A,\delta,q_0,F \rparen \) ,
where:

\[ Q = Q_1 \times Q_2 \] \[ q_0 = \lparen q^1_0, q^2_0 \rparen \] the transition function \( \delta\) is defined by the formula \[ \delta \lparen \lparen q, p \rparen, a \rparen = \lparen \delta_1 \lparen q, a \rparen , \delta_2 \lparen p, a \rparen \rparen \] for every \( q \isin Q_1 \) , every \( p \isin Q_2 \) , and every \( a \isin A \) . And the set of the final states is defined as: \[ F= \lbrace \lparen q,p \rparen | q \isin F_1 \land p \notin F_2 \rbrace \] \( M \) accepts the language \( L_1 \setminus L_2 \) .

Complement #

Suppose \( M = \lparen Q, A, \delta, q_0, F \rparen \) is a complete finite state automaton accepting \( L \) . A complement \( M^c\) is a complete \( \text {FSA} \) \( M^c = \lparen Q,A,\delta,q_0,F^c \rparen \) , where:

\( M^c \) accepts the language \(L\) .

Summary of Operations on FSA #

Suppose \( M_1 = \lparen Q_1, A, \delta_1, q^1_0, F_1 \rparen \) and \( M_2 = \lparen Q_2, A, \delta_2, q^2_0, F_2 \rparen\) are finite state automata accepting \( L_1 \) and \(L_2 \) , respectively. Let \( M \) be the complete \( \text {FSA M} = \lparen Q,A,\delta,q_0,F \rparen \) ,
where:

\[ Q = Q_1 \times Q_2 \] \[ q_0 = \lparen q^1_0, q^2_0 \rparen \] \[ \delta \lparen \lparen q, p \rparen, a \rparen = \lparen \delta_1 \lparen q, a \rparen , \delta_2 \lparen p, a \rparen \rparen \]

The set of final states will be defined as

Exercises #

Part 1 #

Let \( A = \lbrace 0, 1 \rbrace \) be the alphabet.

1. Build a complete \( \text { FSA } M_1 \) that recognises the language: \[ L_1= \lbrace x \isin A^* | x \text { has an even number of } 1's \rbrace \]

   Solution ▾

   

2. Build a complete \( \text { FSA } M_2 \) that recognises the language: \[ L_2= \lbrace x \isin A^* | x \text { has an odd number of } 0's \rbrace \]

   Solution ▾

   

3. Build a complete \( \text { FSA } \) that accepts when either \( M_1 \) or \( M_2 \) accepts.

   Solution ▾

   

4. Build a complete \( \text { FSA } \) that accepts when both \( M_1 \) and \( M_2 \) accept.

   Solution ▾

   

5. Build a complete \( \text { FSA } \) that accepts when \( M_1 \) accepts and \( M_2 \) rejects.

   Solution ▾

   

6. Build a complement for \( M_1 \) .

   Solution ▾

   

Part 2 #

Construct a complement for the following \( \text {FSA} \)

Part 3 #

Let \( A = \lbrace 0, 1 \rbrace \) be the alphabet.

1. Build a complete \( \text { FSA } M_a \) that recognises the language: \[ L_a= \lbrace x \isin A^* | x \text { is the binary representation of an integer, and it is divisible by } 2 \rbrace \]

   Solution ▾

   Graphical Representation - State Transition Diagram

   

   Graphical Representation — State Transition Table

   

2. Build a complete \( \text { FSA } M_b \) that recognises the language: \[ L_b= \lbrace x \isin A^* | x \text { is the binary representation of an integer, and it is divisible by } 3 \rbrace \]

   Solution ▾

   Graphical Representation - State Transition Diagram

   \

   Graphical Representation — State Transition Table

   

3. Build a complete \( \text { FSA } \) that accepts when both \( M_a \) and \( M_b \) accept.

   Solution ▾

   

4. Build a complete \( \text { FSA } \) that accepts when either \( M_a \) or \( M_b \) accepts.

   Solution ▾

   

5. Build a complete \( \text { FSA } \) that accepts when \( M_a \) accepts and \( M_b \) rejects.

   Solution ▾