Mathematization in teaching pumping lemmas
Thérèse Smith, Robert McCartney · 2013
Theory of Computation provides students of the computing disciplines with understanding that some problems are not solvable, and that there is a range of complexities of problems, in terms of significant resources, including but not limited to time and memory. Theory of Computation acquaints students with reasoning processes by which they can know (for some cases) the complexity class of a given problem, and by which they can, for some problems they might find in the future, determine the complexity. People formulate these reasoning processes in symbols, and use logic with quantifiers; an example of this is the application of the pumping lemma for regular languages. We categorized the errors students made in applying the pumping lemma for regular languages, to develop an understanding of the possible misconceptions, in turn, to improve teaching.