CSC 340 Theory of Computing Final Exam
Study Guide Questions and Answers
(GRADED A+)
Which of the following statements are TRUE according to the Pumping Lemma
for a context-free language L? Select all that apply - Answer✔️There is a special
natural number N
Any string w in L with |w| >= N can be written as w = uvxyz
|vxy| <= N
|v| > 0 or |y| > 0
The language L = {a� | n is a prime integer} is context-free - Answer✔️False
The language L = {an bn | n a natural number} is context-free - Answer✔️True
The language L = {a* b*} is context-free - Answer✔️True
The Language L = { an bn cn | n a natural number} is context-free -
Answer✔️False
The language L consisting of all strings with twice as many a's as b's is context-
free - Answer✔️True
The language L = {ww | w � {a , b}*} is context-free - Answer✔️False
The language L = {an (bc)n | n a natural number} is context-free - Answer✔️True
The language L = {an bn cm dm | n, m � N} is context-free - Answer✔️True
We saw a push-down automata where multiple characters were pushed onto the
stack in one transition. - Answer✔️True
The language L = { an b an } is context-free - Answer✔️True
There is a push-down automata whose language L = anbncn - Answer✔️False
, The transition:
(s, a, �), (s, a)
corresponds to: - Answer✔️Push operation
The transition:
(s, �, b), (s, �)
corresponds to: - Answer✔️Pop operation
The transition:
(s, �, �), (f, �)
corresponds to: - Answer✔️Change of state
Turning machines have a built-in stack. - Answer✔️False
A transition of a Turning machine may perform which of the following? Select all
that apply. - Answer✔️Writes a symbol onto tape
Moves one cell to right
Moves one cell to left
A Turning machine consists of which of the following? Select all that apply. -
Answer✔️A finite control unit
An input tape
A head positioned on the tape
Every Turing machine has an initial state which is the state in which the Turing
machine starts - Answer✔️True
The input tape of a Turning machine has a right border and can be extended
indefinitely to the left. - Answer✔️False
The Church-Turing thesis states that every computer algorithm can be
implemented as a push-down automata. - Answer✔️False
The next state of a Turing machine is determined by its current state and the
character under the read/write head. - Answer✔️True
Study Guide Questions and Answers
(GRADED A+)
Which of the following statements are TRUE according to the Pumping Lemma
for a context-free language L? Select all that apply - Answer✔️There is a special
natural number N
Any string w in L with |w| >= N can be written as w = uvxyz
|vxy| <= N
|v| > 0 or |y| > 0
The language L = {a� | n is a prime integer} is context-free - Answer✔️False
The language L = {an bn | n a natural number} is context-free - Answer✔️True
The language L = {a* b*} is context-free - Answer✔️True
The Language L = { an bn cn | n a natural number} is context-free -
Answer✔️False
The language L consisting of all strings with twice as many a's as b's is context-
free - Answer✔️True
The language L = {ww | w � {a , b}*} is context-free - Answer✔️False
The language L = {an (bc)n | n a natural number} is context-free - Answer✔️True
The language L = {an bn cm dm | n, m � N} is context-free - Answer✔️True
We saw a push-down automata where multiple characters were pushed onto the
stack in one transition. - Answer✔️True
The language L = { an b an } is context-free - Answer✔️True
There is a push-down automata whose language L = anbncn - Answer✔️False
, The transition:
(s, a, �), (s, a)
corresponds to: - Answer✔️Push operation
The transition:
(s, �, b), (s, �)
corresponds to: - Answer✔️Pop operation
The transition:
(s, �, �), (f, �)
corresponds to: - Answer✔️Change of state
Turning machines have a built-in stack. - Answer✔️False
A transition of a Turning machine may perform which of the following? Select all
that apply. - Answer✔️Writes a symbol onto tape
Moves one cell to right
Moves one cell to left
A Turning machine consists of which of the following? Select all that apply. -
Answer✔️A finite control unit
An input tape
A head positioned on the tape
Every Turing machine has an initial state which is the state in which the Turing
machine starts - Answer✔️True
The input tape of a Turning machine has a right border and can be extended
indefinitely to the left. - Answer✔️False
The Church-Turing thesis states that every computer algorithm can be
implemented as a push-down automata. - Answer✔️False
The next state of a Turing machine is determined by its current state and the
character under the read/write head. - Answer✔️True
