Lab Session #4 #

Agenda #

Deterministic Pushdown Automaton (DPDA): Notion, formal definition, configuration, transition, and acceptance.
Exercises on DPDAs

Pushdown Automata #

A Pushdown Automaton (PDA) is a way to implement a Context Free Grammar in a similar way we design Finite Automaton for Regular Grammar.

It is more powerful than FSA
FSA has a very limited memory but PDA has more memory
PDA = FSA + a Stack

A stack is a way we arrange elements one on top of another; it does two basic operations:

PUSH: A new element is added at the Top of the stack
POP: The Top element of the stack is read and removed

PDA-components #

A Pushdown Automaton has 3 components:

An input tape
A Finite Control Unit
A Stack of infinite size

Acceptance criteria: A string \(x\) is accepted by a PDA if there is a path coherent with \(x\) on the PDA that goes from the initial state to the final state. The input string has to be read completely.

When a PDA reads an input symbol, it will be able to save it (or save other symbols) in its memory.

For deciding if an input string is in the language \( A_nB_n \) , the PDA needs to remember the numbers of \(a\) ’s.
Whenever the PDA reads the input symbol \(b\) , two things should happen:

it should change states: from now on the only legal input symbols are \(b\) ’s.
it should delete one a from its memory for every \(b\) it reads.

A single move of a PDA will depend on:

the current state,
the next input (it could be no symbol: ε symbol), and
the symbol currently on top of the stack. PDA will be assumed to begin operation with an initial start symbol \( Z_0 \) on its stack
\( Z_0 \) is not essential, but useful to simplify definitions
\( Z_0 \) is on top means that the stack is effectively empty.

Formal Definition #

A Pushdown Automaton is a tuple \( \langle \) \(Q\) , \(I\) , \(\Gamma\) , \(\delta\) , \(q_0\) , \(Z_0\) , \(F\) \(\rangle\) , where:

\(Q\) is a finite set of states.
\(I\) and \(\Gamma\) are finite sets, the input and stack alphabets.
\(\delta\) is the transition function.
\(q_0 \in Q\) , the initial state.
\(Z_0 \in \Gamma\) , the initial stack symbol.
\(F \subseteq Q\) , the set of accepting states.

Configuration A configuration is a generalization of the notion of state. It shows:

the current state,
the portion of the input string that has not yet been read, and
the stack. It is a snapshot of the PDA.

Example #

Construct a PDA that accepts \( L = \{0^n1^n | n \geq 0\} \)

Solution ▾

Exercises #

Part I #

Build DPDAs that recognise the following languages:

\( \{a^nb^{2n} \mid n \ge 1 \} \)
Solution ▾
\( P = \{xycy^Rx^R \mid x \in \{a, b\}^* \wedge y \in \{d, e\}^* \wedge \left\vert{x}\right\vert > 0 \}\) (where \(x^R \) , \(y^R \) are the reversed strings \(x\) , \(y\) ), the alphabet is \(I=\{a, b, c, d, e\}\)
Solution ▾
\( \) The language of nested and balanced brackets and parentheses. E.g. a string in the language: \((([])())()\) , a string that does not belong to the language: \(([(]))()()\) – the alphabet is \(I = \{(, ), [, ]\}\)
Solution ▾

Part II #

Build DPDAs that recognise the following languages:

\(L_1 = \{w \in \{a, b\}^* \mid \phi(w, a) = \phi(w, b)\}\) where \(\phi(s, c)\) is the number of occurrences of the character \(c\) in the string \(s\)
Solution ▾
\(L_2 = \{a^nb^ma^mb^n \mid n > 0 \wedge m > 0\}\)
Solution ▾
\(L_3 = L^*_2\)
Solution ▾
\(L_4 = \{a^{n_1}b^{n_1}a^{n_2}b^{n_2}a^{n_3}b^{n_3} \ldots a^{n_k}b^{n_k} \mid k \ge 1 \wedge n_i \ge 1 \wedge 1 \le i \le k \}\)
Solution ▾

Homework #

Define a DPDA that recognises this language: \(L = \{a^nb^n \cup a^nb^{2n} \mid n \ge 0\}\)
Construct a DPDA that recognises the language of well-formed parentheses of the arithmetic expressions (binary operations).

For simplicity, consider the alphabet \(I = \{a, (, ), +\} \) - a single symbol \(a \) that represents terms \(a, b, c, \ldots \) and a single operator \(+\) .

Examples of strings belonging to the language are:

\((a + a)\)
\(((a) + (a + a))\)
\(((a + a))\)