Automata-XXII

Presented by:
Jaswinder Singh
Department of Computer Science,
Guru Nanak Dev University, Amritsar

continuing 2
Some Languages/Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Pushdown Automata-I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Pushdown Automata-II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Pushdown Automata-III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Pushdown Automata-IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Pushdown Automata-V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Pushdown Automata-VI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Pushdown Automata-VII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

at the end 10
The day ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
And Finally .... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1
continuing 2 / 12

Some Languages/Grammars
Consider the following languages/grammars:
✔ L = {0n 1n : n ≥ 0}.
✔ L = {wwR : w ∈ {0, 1}∗ }, where wR denotes reverse of w.
✔ The grammar G with productions S → aS|aSbS|ǫ.
✔ The grammar G with productions E → E + E|E ∗ E|(E)|id.
Note 1: All of above are languages/grammars requires to remember some event happened during
processing.
Note 2: They are not regular, obeviousely will not be accepted by automata, because automata has
no memory attached with it.
Automata-XXII Jaswinder Singh,
CSL222: Theory of Computer Science DCS, GND University, – 2 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

Pushdown Automata-I

0 1 1 1 1 ... 0
Input
↑
→
Stack

Table 1: Model of the Pushdown Automata(PDA)

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 3 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

2
 Pushdown Automata-II
✔ A pushdown automaton consists of
1. a finite nonempty set of states denoted by Q, P
2. a finite nonempty set of input symbols denoted by :,
3. a finite nonempty set of pushdown symbols denoted by Γ,
4. a special state called the initial state denoted by q0 ,
5. a special pushdown symbol called the initial symbol on the pushdown store denoted by Z0 .
6. a set of final states, a subset of QP denoted by F , and
7. a transition function δ from Q × ( ∪{ǫ}) × Γ to the set of finite subsets of Q × Γ∗ .

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 4 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

Pushdown Automata-III
P P
Example: Let the PDA A = (Q, , Γ, δ, A, Z0 , F ) where Q = {A, B, C}, = {a, b}, Γ = {X, Z0 }, F = {C} and δ is
given by

δ(A, a, Z0 ) = (A, XZ0 ) (1)

δ(A, a, X) = (A, XX) (2)
δ(A, b, X) = (B, ǫ) (3)
δ(B, b, X) = (B, ǫ) (4)
δ(B, ǫ, Z0 ) = (C, Z0 ) (5)

Note 1: The (1) and (2) above express push operation, where top of stack symbol is X.
Note 2: In (3) & (4) above ǫ on RHS express pop operation.
Note 3: In (5) above ǫ on the LHS express input has been exhausted.
Note 4: In (5) above Z0 both on the LHS and RHS express neither push nor pop operation.

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 5 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

3
 Pushdown Automata-IV
(a,Z0 ,XZ0 )

(b,X,ǫ) (ǫ,Z0 ,Z0 )

δ(A, a, Z0 ) = (A, XZ0 ) A B C
δ(A, a, X) = (A, XX)
(a,X,XX) (b,X,ǫ)
δ(A, b, X) = (B, ǫ)
Figure 1: PDA
δ(B, b, X) = (B, ǫ)
δ(B, ǫ, Z0 ) = (C, Z0 )

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 6 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

Pushdown Automata-V

a a a a b b b b
Input
↑
A
→ Z0
Stack

Figure 2: Before δ(A, a, Z0 ) = (A, XZ0 )-move

a a a a b b b b
Input
↑
A → X
Z0
Stack

Figure 3: After δ(A, a, Z0 ) = (A, XZ0 ); Next δ(A, a, X) = (A, XX)

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 7 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

4
 Pushdown Automata-VI

a a a a b b b b
Input
↑ → X
A X
Z0
Stack

Figure 4: After δ(A, a, X) = (A, XX); Next δ(A, a, X) = (A, XX)

a a a a b b b b → X
Input
↑ X
A X
Z0
Stack

Figure 5: After δ(A, a, X) = (A, XX); Next δ(A, a, X) = (A, XX)

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 8 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

Pushdown Automata-VII

a a a a b b b b
Input
↑
C
→ Z0
Stack

Figure 6: After δ(B, ǫ, Z0 ) = (C, Z0 )

Acceptance criteria in PDA

1. Input should have been exhausted.

2. Stack should be empty(or as was avaiable originally)
3. We should be in one of the final state

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 9 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

5
at the end 10 / 12

The day ahead

✔ Automata-XXIII

Automata-XXII Jaswinder Singh,

CSL222: Theory of Computer Science DCS, GND University, – 11 / 12
MCA(FYIC) 4th Semester(2023) Amritsar

And Finally ...

THANKS

I would rather die of passion than of boredom.

–Emile Zola
Automata-XXII Jaswinder Singh,
CSL222: Theory of Computer Science DCS, GND University, – 12 / 12
MCA(FYIC) 4th Semester(2023) Amritsar