Types of Questions in Computer Science Education - Guide to Teaching Computer Science: An Activity-Based Approach - page 177

Table 9.4 Illustration of the types of questions in the context of Automata theory
Type of question An example pattern

Type1: Development of a
solution

Design a finite automaton that recognizes a regular language L

Type2: Development of a
solution that uses a given
module

Given the A1 finite automaton that recognizes the language
L1 and A2 finite automaton that recognizes the language L2,
design a finite automaton that recognizes the language L1 υ L2

Type3: Tracing a given
solution

Given a push down automaton P, and a word w, show the
sequence of states that P goes through while processing w

Type4: Analysis of code
execution

Given a finite automaton A, present
A word that the automaton accepts
A word that the automaton rejects
A word that its processing is terminated in the trap state

Type5: Finding the purpose of
a given solution

Given a Turing Machine T, determine what language it accepts

Type6: Examination of
the correctness of a given
solution

Does the given Turing Machine T recognize the language L?

Type7: Completion a given
solution

Complete the Push Down Automaton P, so it will recognize
the language L

Type8: Instruction
manipulations

Given a Turing Machine T, if the transition from state q1 to
q2 is replaced by the next transition [to be described], what
language will the machine recognize?

Type9: “Efficiency”
estimation

Given a finite automaton A that recognizes the language L, can
you present a different finite automaton that recognizes the
same language with fewer states?

Type10: Question design Design a question that requires the presentation of a BNF

grammar for an irregular language

Type11: “Programming” style
questions

Given three different Push Down Automata that recognize a
language L, examine the automata and state which of them, in
your opinion, is the best. Explain your answer

Type12: Transformation of a
solution

Given a Turing machine T, present a BNF grammar that
expands the same language

The construction of such a table can be facilitated as an activity in the MTCS
course for one of the topics included in the high school curriculum that the MTCS
focuses on.

9.6 Question Preparation

The preparation of questions to be used in a CS class is not a simple task. Many con-
siderations should be thought about, some of them are local to the specific lesson
and class and others are more global and refer to the teaching unit, or even, further,
to the entire curriculum. Those considerations are important and therefore, the pro-