2y ago

31 Views

3 Downloads

914.98 KB

7 Pages

Transcription

6th WSEAS International Conference on EDUCATION and EDUCATIONAL TECHNOLOGY, Italy, November 21-23, 2007115Problems In Understanding Abstract Concepts Related To RegularAnd Context-Free LanguagesZEESHAN ALI RANA, MUHAMMAD ASHRAF IQBAL, YASSER HASHMILahore University of Management Sciences (LUMS)Opposite Sector U, DHA, LahorePAKISTAN{zeeshanr, aiqbal, yasser}@lums.edu.pkAbstract: - Understanding abstract models in automata theory is important in the fields of computer scienceand digital circuit design. In automata theory, problems are categorized in different classes of computability,from simpler to harder. Problems which lie in class of regular languages are simplest kind of problems.Problems which lie in class of context-free languages are relatively harder. Students tend to confuse therelationship between these two classes of languages and between their members. Questions related to theclosure properties of regular and/or context free languages pose particular problems. Students make mistakesperforming operations like intersection, union and concatenation on sets of regular and context-free languages.For this research the students of automata are asked to solve some examination and assignment problemsrelated to closure properties of the above said classes. A questionnaire, seeking descriptive answers, is used tostudy 1) the mental process 2) the structure of mental concept map and 3) line of reasoning followed whileattempting a problem. This study reveals that the students make mistakes because their abstract concepts arenot correctly structured and in particular do not support logical inferences. Students also have a tendency toapply the concepts mechanically instead of applying them meaningfully. Finally, students fail to actuate properconceptual link at proper time.Key-Words: - Abstract Concepts, Motivation, Line of Reasoning, Regular Languages, Context-freeLanguages, Think Aloud.1. IntroductionAutomata and computability theory have a majorrole in understanding of computer science concepts.Circuit designing also needs knowledge of automataconcepts [1]. Automata theory categorizes problemsin sets of simpler problems and harder problems.Simpler problems can be solved using machineswhich do not have any temporary memory.Relatively harder problems can not be solvedwithout memory but can be solved using themachines with stack memory. Such machines can becalled stack machines. The set of simplest problemsis called set of regular languages (RLs) whereas theset of relatively harder problems is called set ofcontext-free languages (CFLs). There are evenharder problems than the context-free languageswhich can not be solved using stack machines. Thispaper only focuses the regular and context-freelanguages and presents the problems noticed duringthe learning of concepts related to the above two setsof languages only. Specifically, the paper portraysthe problems in understanding the set operations likeunion, intersection, complement and concatenationon the sets of regular and context-free languages.The concepts related to computability theoryare considered abstract and cognitively complex [2,3]. In this paper we will follow a definition ofconcepts suggested by Novak [13]. A conceptconsists of a name or a tag used to access theconcept. Stored attached to the tag are attributes orproperties of the concept. It is these properties thatsupport any logical inferences linking a concept withother concepts. In this sense an abstract concept is aconcept whose attributes are not based on specificinstances but rather are based on classes of objects.In other words an abstract concept has propertiesthat refer to other concepts rather than concreteinstances. We regard these abstract concepts asparticularly challenging to learn and to reason about.Thus these concepts are congnitively complexbecause people fail to handle mental manipulationsneeded [3]. Studies reveal that learning abstractconcepts is a difficult task [2, 4] and the cognitivecomplexity is one of the factors causing frustrationand lack of interest to learn [2]. In addition, learningtheories affirm that students construct knowledgeactively and it can not be absorbed passively usingtext books and lectures [6, 7]. So the causedfrustration restrains the students to actively constructthe knowledge and perform meaningful learning.Acknowledging the complexity of the

6th WSEAS International Conference on EDUCATION and EDUCATIONAL TECHNOLOGY, Italy, November 21-23, 2007concepts, students still need to motivate themselvesin order to cope with the frustration and continuelearning meaningfully. In order to keep themselvesmotivated, students set themselves some goalswhich could be achievement goals, learning goalsand performance goals [5]. Goals are set accordingto the student’s approach towards learning. Thisapproach is another factor which affects meaningfullearning. Chin [8] discusses two approaches towardslearning; intrinsic and extrinsic. Intrinsic approach islearning due to a desire and extrinsic approach islearning for the sake of others’ wish, the others canbe parents or teachers [8]. Students with intrinsicinterest seem to have learning goals in their mindsand have interest in studies, and hence are betterlearners. Study by Hazzan [3] exhibits that evensuch good students make mistakes when asked tosolve problems related to abstract concepts. Hazzannotes a strategy where students reasonning withabstract concepts prefer to convert them to concreteexamples. After reasoning with concrete examplesthey translate the inferences reached back to theabstract domain. In other words they reason byexample. We note a similar strategy in our studentsreasoning about automata theory. In addition,Chesnevar et al. [2] beleive that students fail tounderstand concepts particularly when reasoningabout them in real time because their focus is on themechanical application of a rote learnt procedurerather than a meaningful understanding of theconcepts.The basic aim of this study is to find wherethings go wrong in knowledge structure of students.For this reason we collected a set of exam questionswhich target a specific set of links in the student’sconcept map. Automata theory is taught as a corecourse to computer science majors in most of theuniversities. These concepts are used to build furtherknowledge of computer science. So meaningfullearning of these concepts is critical inunderstanding of computer science concepts. Textbooks of Automata theory typically keep theirnarration at the abstract level without linking theseabstract concepts to their concrete instances. Wesuspect that this may contribute to a rote learning ofabsract concepts so that they do not support errorfree logical inferecing nor are students neccessarilyaware of how reasoning must change depending onthe level of abstraction. We further suspect thatsticking to an abstract narration also interferes withthe subjective level of interest of the student. Thisstudy reveals that the abstract narrative of the textbooks leaves some students behind. Specificallythose whose reasoning fluctuates between abstract116concepts and concrete examples and who fail todiscover themselves the contrast between these two.The paper is organized in the following manner.Section 2 gives a brief background needed tounderstand the concepts used in the paper. Section 3discusses the way this research was designed andconducted. Section 4 discusses the results of thestudy and the conclusion is presented in Section 52. BackgroundIn automata theory problems are termed aslanguages and they are categorized into differentclasses with respect to their difficulty level.Formally, a language is a set of strings, for example“set of all the numbers ending with 0” can beconsidered one language and a string is a finitesequence of characters.Regular languages are simplest kind ofproblems. Problems in the class of regular languagescan be solved using finite state machines having notemporary memory. We call such machinesDeterministic Finite Automata (DFA) or NonDeterministic Finite Automata (NFA) in our conceptmap in figure 1. For example, counting the numberof instances of a character in a particular string,determining whether a number is even or odd aremembers of this class.Class of context-free languages includes all themembers of regular languages as well as somerelatively harder problems. The more sophisticatedkind of counting will fall into this category. Likedetermining whether every open brace has acorresponding closing brace in the program ordetermining whether a string is reverse of itself arekind of problems this class contains. Solution tosuch problems needs some temporary memory tostore information. These solutions can be obtainedby using finite state machines having stack memoryonly. We call such machines as Push-DownAutomata (PDA) in our concept map in figure 1.Closure properties of a class show whichoperations on members of a class will yield themember of the same class. If an operation on anytwo members of a set always yields an element ofthe same set, then that set is said to be closed underthe performed operation [9, 10]. For example the setof natural numbers is closed under addition but isnot closed under division [10]. Similarly the sets ofregular languages and context-free languages havesome closure properties as well. Regular languagesare closed under union, intersection, complement,concatenation and some other operations. In thispaper we will focus on the above listed four

6th WSEAS International Conference on EDUCATION and EDUCATIONAL TECHNOLOGY, Italy, November 21-23, 2007117Fig. 1 Concept Map Showing the Relationship of Classes of Languages and the Tools Used to Solve Themoperations only. Context-free languages are closedunder union and concatenation but complement of acontext- free language may fall outside the class ofcontext-free languages. Similarly intersection of twomembers from the class of context-free languagesmay not yield a member from the same class.The concept map regarding relationship of thelanguages and the tools needed to solve theproblems of each class is shown in figure 1. It showshow the automata theory concepts are linkedtogether and the structure expected in a student'smind. The links are numbered in the figure just torefer them in coming sections.groups and pooled the results.3.1 Research HypothesesOur research hypotheses are:1 For some questions ability to generate the rightconcrete example will lead to a succesfultranslation of inferences at the abstract level andthe correct answer. Here ability to generate anexample will predict a correct answer.2 In some questions reasoning using concreteexamples is more likely to lead to an incorrectinference at the abstract level. Here usingexamples will hinder reaching a correct answer.3 Lack of motivation is a hindrance in learning ofthese concepts.3. Research DesignWe collected data of 30 students of the courseAutomata and Complexity Theory taught at LahoreUniversity of Management Sciences, Lahore,Pakistan in academic year 2006-07. The class was ahybrid of graduate and 4th year undergraduatestudents. We made no distinction between these3.2 Examination, Assignment and ThinkAloud Interviews QuestionsWe collected 10 questions from assignment and midterm of Automata offered at LUMS, Lahore,Pakistan. These questions were related to closureproperties and relationship of classes of languages.

6th WSEAS International Conference on EDUCATION and EDUCATIONAL TECHNOLOGY, Italy, November 21-23, 2007118Table1 Questions Asked In Examination and AssignmentQ. #Q. 1Q. 2Q. 3Q. 4Q. 5Q. 6Q. 7Q. 8Q. 9Q. 10QuestionsState whether True or False. Justify your answer to get any credit.Complement of a CFL may be non-CFLIntersection of a regular language and CFL is always a regular languageConcatenation of a regular language and a CFL is always CFL, but not regularL4 L1 L2 L3, where L1 and L2 are regular and L3 is CFL. It is possible that L4 will be a RLLet L4 L1 L2 L3. If L1 and L2 are regular and L3 is not regular, it is possible that L4 is regularL2 Complement of L1, where L1 is a CFL. It is possible that L2 will be a regular languageL4 L1UL2UL3, where L1, L2, L3 are regular languages. L4 will always be a context free languageIntersection of two non-regular languages is always non-regularIntersection of two CFL’s is CFLSubset of a CFL is always a CFLTable 2 Questions Asked In Think Aloud InterviewsQ. #Q. 1Q. 2Q. 3Q. 4Q. 5Q. 6Q. 7Q. 8Q. 9Q. 10QuestionsA coin counter which counts 6 coins of value 5. Is it a regular language (RL) solver?A soda ‘can’ releaser which releases a ‘can’ if input is 1. Does this releaser solve a regular language?Make a dispenser which takes coins of value 5 as input, counts if there are 6 coins entered and if yes then release a ‘can’. Use the abovetwo machines to make the dispenser. Which operation do you need to perform?Is the problem solved in Q. 3 a regular language? Take its union with any CFL. Will the results be regular ever? Which example did youthink while taking union and why?A robot which identifies red balls and separate outs them from balls of all colors. Is the problem solved by the robot a regular language?If the robot needs to separate out as many red balls as blue balls, will it be a regular language?The above told dispenser now asks even number of questions before asking you for money. If you answer more than 50% questionscorrectly, then it releases a soda can without asking for money. Is it a RL? Or CFL but not RL?If you answer 50% of the questions correctly then it asks you to enter 10 rupees and on entering coins which sum up to 10 rupees, itreleases a soda ‘can’. Was there any additional machine in the dispenser of Q. 3? Which operation was performed if some additionalmachine has been added?If you answer less than 50% correctly then it asks for full payment to release a soda ‘can’. Which operation you perform this time ifsome additional machine is added?Are the machines in Q. 8 and Q. 9 collectively the complement of the machine in Q. 7? Will the complement be a CFL?Table 1 lists the questions asked in the exam and theassignment. Q1 in table 1 can be solved withoutusing an example and can even be rote learnt sinceit is a property of the class of CFLs. Q2 targets thelinks 5, 7, 8, 13 and 16 of figure 1. It is the propertyof languages that intersection of a DFA and a PDAwill always be a PDA and a PDA can solve thesimplest problems as well. An example is notneeded to solve the problem. Q3 and Q4 target thelinks 5 and 7 whether the students use this link atappropriate time. This question again does not needuse of example but if a student picks a languagewhich belongs to class of regular languages, he / shecan solve the problem. Furthermore, Q4 attempts tocheck whether students know if regular languagesare closed under intersection or not. For Q5,students need to conceptualize the resultingconcatenated language which they should finddifficult if they do not use an example. The reasonof the difficulty is that here are many abstractconcepts to cater and making inference betweenthem at abstract level will be a difficult task. Q6checks the students’ knowledge on the property ofregular language that they are closed undercomplement. Q6 can easily be solved without usingexamples. Q7 simply checks if students can identifythe relationship between the classes of CFLs andRLs, in addition it checks closure property of RLs.This question is a simple question and if thestudents have the links 4, 5 and 7 in their conceptmap they can solve the problem without anyexample. Q8 asks students to think abstractly aboutthe class of regular and non-regular languages. Weexpect that students using the examples will becomfortable solving this problem. Q9 is a straightforward question related to one property of CFLs.Even the students who rote learnt the property cananswer the question, and we do not expect thatstudents will use examples. Q10 checks whetherstudents can differentiate between the problemsregarding relationships between the classes oflanguages and relationship between the members ofthe languages. This question further tries to find atwhat abstraction level the students think.We conducted five think aloud interviews tocheck motivation of students towards automata andthe mental process followed while solving theproblems related to automata. Table 1 provides theseries of questions asked during the think aloudinterviews. In addition, the students were explicitlyasked why they feel it difficult to comprehend theseconcepts.

6th WSEAS International Conference on EDUCATION and EDUCATIONAL TECHNOLOGY, Italy, November 21-23, 2007119Use of Examples for Solving QuestionsStudents Response to Exam QuestionsUsed Examples100Incorrect%age of students%age of Q8Q9Q10Question No.Fig. 2 Students’ Response to Examination andAssignment Questions4. Results and DiscussionThe analysis of the examination results show verystrong tendency to reduce the abstraction level of theproblems by using examples. Some proportion ofstudents generated concrete examples for everyquestion. Overall questions can be divided into thosefor which concrete reasoning helped, those forwhich it hindered, and those that can be answered byrote learnt knowledge. Figure 2 shows response ofstudents on each question. Figure 3 shows whatpercentage of students used examples for solvingquestions. Students particularly faced problems inQ3, Q5, Q8 and Q10. Approximately 61% of thewrong answers came from these four questions.Q3, Q5, Q8 and Q10 are the questions whichdemand extra attention of the student and need thestudent to have good understanding of theunderlying concept. It needs the existence andactuation of proper links in the mental concept mapof the student. Bars of Q3 and Q5 in figure 2 suggestthat students particularly face problems whileperforming concatenation. Figure 3 shows that thestudents who tried the Q8 and Q10 by thinking of anexample, most of them reached the correct solution.For Q8 and Q10 more than 65% of the studentsusing examples got correct answers. These are thekind of questions for which concrete reasoninghelped. The students failed to provide properreasoning when they handled them at abstract leveland tried to make inference between abstractconcepts instead of reducing the abstraction level.Q5 is another indication of problem to studentswhen they do not use examples and try to makeinference between abstract concepts but in this casethe use of concrete reasoning hinders instead ofhelping the student. In such scenarios the studentsneed to be capable of handling a certain level ofabstraction. Q3 also falls in the same category Q5does. Use of examples does not always help studentsQ1Q2 Q3 Q4 Q5Q6 Q7 Q8 Q9 Q10QuestionsFig. 3 Use of Examples for Solving Questionsreach the correct solution. It further needs properknowledge of the underlying concept to buildconcrete reasoning on.Q1, Q2, Q4, Q7 and Q9 are the questionswhich can be answered by rote learnt knowledge ofclosure properties of regular laguages. Figure 3shows that a significant number of students tried touse examples to solve even such simpler problems.Only Q7 was answered without examples andcorrect solution was reached. Figure 4 shows that100% of the students who used an example to solveQ7 got it wrong. These wrong attempts were madeby students following the mental process studied byHazzan [3]. Hazzan narrates that while handlingabstract concepts, students unconciously try toreduce the abstraction level of the concept [3]. Sincethis was a trivial problem and a simple property ofregular languages could have been used as done bymost of the students. This is the kind of question forwhich the concrete reasoning did not help. Thestudents who did not have good understanding of theproperty tried to prove their claim using an examplewhich is a wrong technique. This brings us toanother deduction which needs further investigation,that these students might even do not know thatpresenting an example is not the proof of the claim.So we infer that students tend to use exampleswithout realizing that this problem can be solvedwithout an example and the use of example hindersinstead of helping the student. On basis of the dataother than Q7, we further infer that students whoattempt a question by first finding examples aremore likely to find correct solution. Wrong attemptsto Q1 were relatively higher as compared to other 4similar questions discussed above. So we includedquestions related to complement of a CFL andconcatenation in think aloud interviews.We explored the mental maps of a subset ofthese students using think aloud protocol. The data

6th WSEAS International Conference on EDUCATION and EDUCATIONAL TECHNOLOGY, Italy, November 21-23, 2007from these flashes out the details of the kinds ofreasoning we have been mentioning. We also use itto support our idea that purely abstract text bookmaterial subjectively hinders learning by loweringmotivation.Taking a detailed example first one finding ofthe think aloud was that whenever the students areasked to think about a CFL, they come up with thelanguage anbn, which sometimes causes problems insolving a problem. For example while answering Q4of table 2, four out of five interviewees thought ofanbn at first. This line of reasoning was leadingthem to the wrong solution. But afterwards theyrealized that they can also pick a regular language totake union with and reached the correct solution.This result supports our hypothesis 2. The reason ofthinking anbn whenever one talks about a CFLmight be that the concept CFL has been closelyassociated with concept anbn. Another reason couldbe that anbn is acting as a label of concept CFL.This claim needs further research and we keep it forfuture work. One of the subjects involved in thinkaloud interviews faced very little problems incomprehending abstract concepts. This led us to adeduction that the understanding of these conceptsalso depends on the quality of the relationshipbetween the object of thought and the thinkingperson as described by previous studies [3, 11, 12].The think aloud interviews suggested thatstudents fail to see any concrete application ofautomata concepts which is a factor hinderingmeaningful learning and is responsible for lack ofmotivation. Unless the students see somethingworking or at least have a feeling that there exists athing similar to what they are being taught, they cannot make significant learning about the taughtconcepts. This result backs our hypothesis 3.Correct Vs Incorrect Comparison on UsingExamples12010080%age of60students40200Total %age of ExamplesUsedCorrect Answers UsingExamplesIncorrect Answers UsingExamplesQ1Q3Q5Q71205. ConclusionLearning abstract concepts is a difficult task. Thisstudy shows that students face problems whilemaking inference between one or more abstractconcepts and they find it easy to solve when theyuse examples to solve the questions. This paperstudies the response of 30 students to exam andassignment questions. The students’ response showsthat whenever they try attempting the problem usingan example, most of the times they end up with acorrect solution. But, in order to reduce the level ofabstraction of the concept, they sometimes tend touse examples where examples are not even needed.Result of Q7 is an example of such a scenario. Theydo so firstly, because they fail to handle the abstractconcepts and secondly because they do not knowwhen to use examples and when not. While provingsomething students should not be using examples,whereas if they are disproving something, they canuse examples. The results of exam questions supporttwo out of three hypotheses. Moreover, the resultsdepict that students face particular problemshandling questions related to intersection andconcatenation of RLs and CFLs. This paper alsosummarizes the results of 5 think aloud interviewswhich were conducted to study the mental process,the structure of the concept map and the line ofreasoning followed while attempting a problem. Theresults of think aloud interviews suggest that lack ofmotivation is a hindrance in meaningful learning ofabstract concepts in automata, hence provinghypothesis 3. Briefly, students fail to make inferencebetween two or more abstract concepts, proper linksare not actuated at proper time and students feel lessmotivated while learning automata since they do notdirectly see any application of these concepts. Thinkaloud interviews showed that students think of anbnwhenever they are told to think about a CFL. Ourfuture direction is the study of the reason whichcompels them to think like that.Acknowledgements:We would like to thank Dr. Shahab Baqai and MalikJahan Khan who are respectively the Instructor andTA of the course Automata offered at LUMS, toprovide the data for analysis.Q9QuestionsFig 4 Use of Examples for Correct and IncorrectAnswersReferences:[1] J. E. Hopcroft, R. Motwani, J. D. Ullman,Introduction to Automata Theory, Languagesand Computation, Second Edition.[2] C. I. Chesnevar, A. G. Manguitman, M. P.Gonzalez, M. L. Cobo, Teaching Fundamentalsof Computing Theory: A Constructivist

6th WSEAS International Conference on EDUCATION and EDUCATIONAL TECHNOLOGY, Italy, November 21-23, 2007[3][4][5][6][7][8][9][10][11][12][13]Approach, JCS&T, Vol 4, No 2, August 2004,pp 91-97.O. Hazzan, Reducing Abstraction Level whileLearning Computability Theory Concepts, InProceedings of ACM ITiCSE,Denmark, Jun 2426 2002, pp 156-160.M. H. Hoffmann, An Engineering Model ofLearning, In Proceedings of 35th is, IN,, Oct 19-22 2005.T. J. Cooney, C. R. Hirsch, Motivation: ingandLearningMathematics in the 1990s, August 1990, pp100-102.M. Ben-Ari, Constructivism in computerscience education, Journal of Computers inMathematics & Sc. Teaching, 20(1):45–73,2001.R. Davis, C. Maher, and N. Noddings. (Eds.)Constructivist views of the teaching andlearning of mathematics. Nat. Council forTeaching Mathematics, 1990.S. K. Chin, A Practical Model for ImprovingStudent Learning of a Programming Language,In Proceedings of 36th ASEE/IEEE FrontiersinEducation Conference,San Diego, CA , Oct 2831 2006.URL:http://math.youngzones.org/Math 2213 webpages/vocabulary2213.html Website visited onMay 8, mlWebsite visited on May 8, 2007.D. C. Aharoni, S. Ergo, Cognitive Processes ofStudents Dealing with Data Structures, InProceedings SIGCSE 2000, Austin, 2000, pp26-30.J. Perrenet, E. Kaasenbrood, Levels ofAbstraction in Students’ Understanding of theConcept of Algorithm: theQualitativePerspective, In Proceedings of ACM ITiCSE,Italy, Jun 26-28 2006, pp 270-274J. D. Novak, Learning, Creating and UsingKnowledge, Lawrence Erlbaum Associates Inc.1998.121

closure properties of regular and/or context free languages pose particular problems. Students make mistakes performing operations like intersection, union and concatenation on sets of regular and context-free languages. . Complement of a CFL may be non-CFL Intersection of a regular language and CFL is always a regular language

Related Documents: