Switching Theory and
Models of Computation
Tutorial Eight:
Introduction to CFG +
Conversion From CFG to PDA +
PDA Design for Counting Techniques
Lecture Instructor : Prof. Dr. Ahmed El Nahas
Tutorial Instructor: Eng. Ahmed Abdelhamid Waheed Abdelwahab
1
Quick Review: Grammar
2
Quick Review: Grammar Types
Turing Machines
Linear Bounded Automata
Push Down Automata
Finite-State Machines
3
Context Free Grammars: Sentence Derivations
4
Exercises (1)
1. Given the grammar G=({a, b}, {S, B}, P, S) where P is given by:
S SaB S aB
B bB B Ԑ
Show Derivation Steps for the following strings :
a) “aaaa”
b) “aabb”
5
Illustration
6
Solution
a)”aaaa”
• S⟹SaB
• ⟹SaBaB
• ⟹SaBaBaB
• ⟹aBaBaBaB
• ⟹aaBaBaB
• ⟹aaaBaB
• ⟹aaaaB
• ⟹aaaa
8 Derivation Steps
7
Solution(2)
b)”aabb”
• S⟹SaB
• ⟹aBaB
• ⟹aaB
• ⟹aabB
• ⟹aabbB
• ⟹aabb
6 Derivation Steps
8
Exercises (2)
2. Given the grammar G=({a, b}, {S, B}, P, S) where P is given by:
S SaB S Sa S aB S a
B bB B b
Show Derivation Steps for “abab”
9
Illustration
10
Solution
b)”aabb”
• S⟹SaB
• ⟹aBaB
• ⟹abaB
• ⟹abab
4 Derivation Steps
11
Quick Review: PDA
12
Quick Review: PDA(2)
13
Notation for PDAs
Remarks:
• If a=Ԑ, it means read nothing from input string.
• If b=Ԑ, it means pop nothing from stack.
• If c=Ԑ, it means push nothing into the stack.
14
Conversion From a Given CFG to PDA
15
Conversion From a Given CFG to PDA(2)
For every terminal σ For a production Yx1x2..xk
σ, σ/Ԑ Ԑ,Y/xk…x2x1
Ԑ, Ԑ/$S Ԑ, $/Ԑ
qstart qloop 3
qaccept
16
Exercises (3)
3. Construct PDA P for the following CFG (the start symbol is S):
S aTb S b
T Ta T Ԑ
17
Illustration-a
18
Illustration-b
19
Solution
qstart
a, a/Ԑ Ԑ, Ԑ/$S
b, b/Ԑ
qloop Ԑ, S/bTa
Ԑ, S/b
Ԑ, T/aT
Ԑ, $/Ԑ Ԑ, T/Ԑ
qaccept
3
20
Exercises (4)
4. Construct non-deterministic top-down PDA to accept the language
defined by the context-free grammar G = ( { A ,B, C, D } , {x , y , z } ,
P, D)
Where P consists of :
• D xyA
• A BC
• C zBC CԐ
• Bx
21
Illustration
22
Solution
qstart
x, x/Ԑ Ԑ, Ԑ/$D
y, y/Ԑ
z, z/Ԑ
qloop Ԑ, D/Ayx
Ԑ, A/CB
Ԑ, C/CBz
Ԑ, $/Ԑ Ԑ, C/Ԑ
Ԑ, B/x
qaccept
3
23
Exercises (5)
5. Construct non-deterministic top-down PDA to accept the language
defined by the context-free grammar G = ( { A ,B} , {0, 1, #} , P, A)
Where P consists of :
• A 0A1 A B
• B #
Trace your PDA for the string “00#11”
24
Illustration
25
Solution
qstart
0, 0/Ԑ Ԑ, Ԑ/$A
1, 1/Ԑ
#, #/Ԑ
qloop Ԑ, A/1A0
Ԑ, A/B
Ԑ, B/#
Ԑ, $/Ԑ
qaccept
3
26
Solution(2)
b)”00#11”
• A⟹0A1
• ⟹00A11
• ⟹00B11
• ⟹00#11
27
Solution(3)
Move # (Move) Current State Stack Input Next State
Initially qstart Ԑ 00#11 qloop
1 (Ԑ, Ԑ/$A) qloop $A 00#11 qloop
2 (Ԑ, A/1A0) qloop $1A0 00#11 qloop
3 (0, 0/Ԑ) qloop $1A 0#11 qloop
4 (Ԑ, A/1A0) qloop $11A0 0#11 qloop
5 (0, 0/Ԑ) qloop $11A #11 qloop
6 (Ԑ, A/B) qloop $11B #11 qloop
7 (Ԑ, B/#) qloop $11# #11 qloop
8 (#, #/Ԑ) qloop $11 11 qloop
9 (1, 1/Ԑ) qloop $1 1 qloop
10 (1,1/Ԑ) qloop $ Ԑ qaccept
11 (Ԑ, $/Ԑ) qaccept Ԑ Ԑ -
Accept
28
Design Problems
Remark: Stack is used for
counting,
and comparison with input string using unary comparison i.e.
symbol by symbol
29
Exercises (6)
6. Construct non-deterministic top-down PDA that recognizes the
language {1n0n , n>0}
Trace your PDA for “1100”
30
Illustration
31
Solution
1, Ԑ/1 0, 1/Ԑ
Ԑ, Ԑ/$ 0, 1/Ԑ Ԑ, $/Ԑ
q0 q1 q2 q33
32
Solution(2)
Move # (Move) Current State Stack Input Next State
Initially q0 Ԑ 1100 q1
1 (Ԑ, Ԑ/$) q1 $ 1100 q1
2 (1, Ԑ/1) q1 $1 100 q1
3 (1, Ԑ/1) q1 $11 00 q2
4 (0, 1/Ԑ) q2 $1 0 q2
5 (0, 1/Ԑ) q2 $ Ԑ q3
6 (Ԑ, $/Ԑ) q3 Ԑ Ԑ -
Accept
33
Exercise (7)
7. Construct non-deterministic top-down PDA that recognizes the
language {1n0n , n≥0}
34
Illustration
35
Solution
1, Ԑ/1 0, 1/Ԑ
Ԑ, Ԑ/$ 0, 1/Ԑ Ԑ, $/Ԑ
q0 q1 q2 q33
36
Exercise (8)
8. Construct non-deterministic top-down PDA that recognizes the
language L={ω ϵ {0, 1}* | ω has the same number of 0’s and 1’s}
37
Illustration
38
Solution
39
Exercise (9)
9. Construct non-deterministic PDA to accept the language containing
all even length palindromes over the alphabet Ʃ ={ a, b, c } {ωωR}.
40
Illustration
41
Solution
a, Ԑ/a
b, Ԑ/b
c, Ԑ/c
Ԑ, Ԑ/$
q0 q1
Ԑ, Ԑ/Ԑ
Ԑ, $/Ԑ
q33 a, a/Ԑ
q2
b, b/Ԑ
c, c/Ԑ
42
Exercise (10)
10. Construct non-deterministic PDA to accept the language containing
all palindromes over the alphabet Ʃ ={ a, b, c } {ω=ωR}.
43
Illustration
44
Solution
a, Ԑ/a
b, Ԑ/b
c, Ԑ/c
Ԑ, Ԑ/$
q0 q1
Ԑ, Ԑ/Ԑ
a, Ԑ/Ԑ
b, Ԑ/Ԑ
c, Ԑ/Ԑ
Ԑ, $/Ԑ
q33 a, a/Ԑ
q2
b, b/Ԑ
c, c/Ԑ
45
Exercise (11)
11. Construct non-deterministic PDA to accept the language containing
{0n1m0m1n | n≥0, m≥0}.
46
Illustration
47
Solution
0, Ԑ/0 1, Ԑ/1
Ԑ, Ԑ/$ Ԑ, Ԑ/Ԑ
q0 q1 q2
Ԑ, Ԑ/Ԑ
1, 0/Ԑ
0, 1/Ԑ
Ԑ, $/Ԑ
Ԑ, Ԑ/Ԑ
q35 q4 q3
48
Exercise (12)
12. Construct non-deterministic top-down PDA that recognizes the
language {aibjck | i=j or i=k, i,j,k ≥ 0}
49
Illustration
50
Solution
51
Exercise (13)
13. Construct non-deterministic top-down PDA that recognizes the
language {aibjck | i=j+k, i,j,k ≥ 0}
52
Illustration
53
Solution
a, Ԑ/a b, a/Ԑ c, a/Ԑ
Ԑ, Ԑ/$ Ԑ, Ԑ/Ԑ Ԑ, Ԑ/Ԑ
q0 q1 q2 q3
Ԑ, $/Ԑ
q33
54
Exercise (14)
14. Construct non-deterministic top-down PDA that recognizes the
language {aibjck | i=j+k, i,j,k > 0}
55
Illustration
56
Solution
a, Ԑ/a b, a/Ԑ c, a/Ԑ
Ԑ, Ԑ/$ b, a/Ԑ c, a/Ԑ
q0 q1 q2 q3
Ԑ, $/Ԑ
q33
57
Exercise (15)
15. Construct non-deterministic top-down PDA that recognizes the
language L over alphabet {a, b, c} such that number of a’s is equal to
sum of b’s and c’s.
58
Illustration
59
Solution
Ԑ, Ԑ/$ Ԑ, $/Ԑ
q0 q1 q22
a, Ԑ/a
a, b/ Ԑ
a, c/ Ԑ
b, Ԑ/b
b, a/Ԑ
c, Ԑ/c
c, a/Ԑ
60
Exercises (16)
16. Construct non-deterministic top-down PDA that recognizes the
language {0i1j | i≤j≤2i, i ≥ 0}
61
Illustration
62
Solution
63
Solution(2)
64
Solution(3)
65
