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:

1. it should change states: from now on the only legal input symbols are $b$ ’s.
2. 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:

1. $\{a^nb^{2n} \mid n \ge 1 \}$
   Solution ▾

   
2. $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 ▾

   
3. $$ 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:

1. $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 ▾

   
2. $L_2 = \{a^nb^ma^mb^n \mid n > 0 \wedge m > 0\}$
   Solution ▾

   
3. $L_3 = L^*_2$
   Solution ▾

   
4. $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 #

1. Define a DPDA that recognises this language: $L = \{a^nb^n \cup a^nb^{2n} \mid n \ge 0\}$
2. 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))$