Lab Session #6 #

Agenda #

PDT - Push-Down Transducer

PD Transducer #

Formal definition #

A Pushdown Transducer (PDT) is a tuple \( T = ⟨Q, I, Γ, δ, q_0, Z_0, F⟩ \) where:

\(Q\) is a finite set of states.
\(I\) and \(Γ\) are the finite sets, the input and stack alphabets.
\(δ\) , the transition function, is a partial function from \( (Q)×(I \cup \{ε\}) × (Γ) \) to the set of finite subsets of \((Q)×(Γ^*)\)
\(q_0 \in Q\) is the initial state.
\(Z_0 \in Γ\) is the initial stack symbol.
\(F \subseteq Q\) is the set of accepting states.
\(O\) is the output alphabet.
\(η : Q×(I \cup \{ε\})× Γ → Q^*\)

Exercises - Part 1 #

Build PDT that accepts \( x \in L_1 \) where \(L_1 = \{a^nb^m | n \geq 1 \wedge n \leq m\}\) and translates it into \( a^nb^n \)
Build PDT that recognizes \( L_2 = \{xc | x \in \{a, b\}^+\} \) and reverses it

Solutions:

Expand ▾

Solution(1):

A PDT that accepts \( x \in L_1 \) where \(L_1 = \{a^nb^m | n \geq 1 \wedge n \leq m\}\) and translates it into \( a^nb^n \)

Solution(2):

A PDT that recognizes \( L_2 = \{xc | x \in \{a, b\}^+\} \) and reverses it

Exercises - Part 2 #

Build DPDT that accepts the following laguages:

\( L_1 = \{a^nb^ma^n | n \geq 1 \wedge m \geq 1\}\) , and translates it into \(a^nb^m \)
\( L_2 = \{a^ib^jc^k | i, j, k \in \mathbb{N} \) and \( i + k = j\} \) , and translates it into \(a^ib^ic^k\)
\(L_3 = \{xcy | x, y \in \{a, b\}^* \wedge |x| > 0 \wedge |y| > 0 \wedge y \neq x^R\} \) , (where \( x^R \) is the reversed string \( x \) ), the alphabet is \(I = \{a, b, c\} \) and translates it into \( y \)
\(L_4 = \{a^nb^m | m, n \in \mathbb{N} \) and \( n \leq m \leq 2n\} \) , and translates it into \(a^nb^n\)

Solutions:

Expand ▾

Solution(1):

A PDT that accepts \( L_1 = \{a^nb^ma^n | n \geq 1 \wedge m \geq 1\}\) , and translates it into \(a^nb^m \)

Solution(2):

A PDT that accepts \( L_2 = \{a^ib^jc^k | i, j, k \in \mathbb{N}\ and\ i + k = j\} \) , and translates it into \(a^ib^ic^k\)

Extra exercise (optional) #

Consider the language of well-formed parentheses of the arithmetic expressions (binary operations). Examples of strings belonging to the language are:

\( (a + b) \)
\( ((a) + (b + c)) \)
\( ((a + b)) \)

Build PDT that recognises this language and translates it into reverse polish notation. For simplicity, consider the following alphabet \( I = \{a, (, ), +\} -- \) a single symbol (‘a’) that represents terms ‘a’, ‘b’, ‘c’, \( \ldots \) . And a single operator (’+’).