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 #

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$

2. Build PDT that recognizes $L_2 = \{xc | x \in \{a, b\}^+\}$ and reverses it

Solutions:

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:

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 (’+’).