"The brontosaurus moved deeper into the swamps when the mammals took over the forest, but one day it ran out of swamps."
BRINGING THE THEORY OF COMPUTATION TO PRIMARY & SECONDARY SCHOOL CHILDREN ....
THE PROOF OF THE PUDDING IS IN THE EATING
HINTS AND SOLUTIONS TO GATE QUESTIONS ON THE THEORY OF COMPUTATION for GATE students in INDIA
PROF. C A R HOARE,FRS VISITED
INDIA. WHILE STROLLING ON THE LAWNS OF TIFR, BOMBAY, HE POINTED OUT THAT CONCEPTS
IN COMPUTER SCIENCE WERE BASICALLY VERY SIMPLE, THEY HAD BEEN MADE ARTIFICIALLY
DIFFICULT AND THAT HE WOULD
SPEND THE REST OF HIS LIFE MAKING THEM SIMPLE.
THE GOEDEL TURING SOCIETY WAS FORMED TO MAKE THE CONCEPTS OF THE THEORY OF COMPUTATION UNDERSTOOD BY COMMON SENSE EXPLANATIONS. AS PART OF THIS PROJECT EXPERIMENTS ARE BEING CONDUCTED WITH B.TECH/BE/MCA/MSC STUDENTS IN THEIR FINAL YEAR TO EXAMINE ANEW THE CONCEPTS OF THE THEORY OF COMPUTATION FROM A COMMON SENSE ANGLE. THIS EXPERIMENT HAS NOW BEEN TRIED OUT ON A COUPLE OF THOUSAND STUDENTS. THE LEVEL OF THEORY OF COMPUTATION HAS BEEN CHOSEN TO BE THE GATE LEVEL REQUIREMENTS OF THE THEORY OF COMPUTATION. THE GATE IS AN ENTRY LEVEL QUALIFYING EXAMINATION CONDUCTED IN INDIA FOR ADMISSION TO SOME OF THE LEADING INSTITUTIONS. THE STANDARD TEXT FOR THE SAME USED IS THE CINDERELLA BOOK(OLD VERSION).
BEAR IN MIND THAT THE AUDIENCE CONSISTS OF STUDENTS DRAWN PRIMARILY FROM A FEUDAL AGRARIAN SOCIETY WITH JUST A TRACE OF EXPOSURE TO THE INDUSTRIAL AND INFORMATION REVOLUTIONS. THE CULTURAL BACKGROUND OF THE STUDENTS IS SMALL TOWN AND RURAL AND MAY LACK THE SLICKNESS OF MAJOR URBAN ENVIRONMENTS. THE ECONOMIC ENVIRONMENT MAKES ONLY ACCESS TO A COMMON PC COMMON RATHER THAN RARE.
THE BASIC LONG TERM AIM OF THE BULK OF THE AUDIENCE IS A DECENT JOB WITH A DECENT MATERIALISTIC LIFE. THE STARS ARE NOT THE TARGET BUT FOR A HANDFUL OF THE STUDENTS.
IT TOOK ME TWENTY YEARS TO REALLY ACCEPT THAT PROF.C.A.R. HOARE'S
COMMENT IS VALID VERY MUCH EVEN FOR THE AREAS OF THE ANALYSIS OF ALGORITHMS AND
THE THEORY OF COMPUTATION.
THE PROOF OF THE PUDDING IS IN THE EATING
IN MY EXPERIMENTS I HAVE MODELS USED FOR UNDECIDABILITY, COMPUTATIONAL COMPLEXITY AND INTRACTABIITY TO MAKE THE CONCEPTS COMMON SENSE AND TRIVIAL. THE RATIONAL MODELS ARE BASED ON THE GOLDEN GOOSE OF THE EXACT COVER PROBLEM. A GREAT DEAL OF THE MATHEMATICS OF COMPUTATION CAN BE EXPLAINED BY INSTANTANEOUS DESCRIPTIONS. THESE CAN BE CONSIDERED TO BE MODELING THE OUTSOURCING SITUATION OR A ANCIENT CLASSIC PRODUCTION OF SNOW WHITE AND THE SEVEN DWARFS. THE EXACT COVER PROBLEM CAN BE USED AS A SCAFFOLDING FOR ALL SUCH COMPUTATIONS. THE PROOFS AND CONSTRUCTIONS HAVE ONLY BEEN TACKLED FOR A COUPLE OF DOZEN PROBLEMS. I ANTICIPATE THAT IN A FEW YEARS TIME TO A DECADE OF TIME I SHOULD HAVE FIGURED OUT THE REQUIRED COMMONSENSE EXPLANATIONS WHICH MAY BE VALID IN MY ENVIRONMENT.
COMMON SENSE DEPENDS ON THE ENVIRONMENT, THE CULTURAL BACKGROUND, THE GEOGRAPHIC LOCATION, THE ECONOMIC LEVELS ETC ETC. SO WHAT IS COMMON SENSE IN ONE PART OF THE WORLD MAY NOT APPLY IN SOME OTHER PART OF THE WORLD.
A MAJOR SOURCE OF COMMON SENSE EXPLANATIONS IS TO REDUCE THE RIGOR WITH WHICH A PROBLEM IS STATED OR A PROOF IS EXPLAINED. ANOTHER MAJOR SOURCE WHICH HAS AN ENORMOUS USE IN THE THEORY OF COMPUTATION IS TO DRAW PARALLELS FROM THE LOCAL MYTHS, LEGENDS AND FOLKLORE.
NONDETERMINISM, COMPUTATIONAL COMPLEXITY AND INTRACTABILITY BECOME TRIVIAL COMMONSENSE CONCEPTS IF WE BEND RATIONALISM A WEE BIT, IN ANY CULTURE OR RELIGION. A WEE BIT OF ACCEPTED LEGENDS AND MYTHOLOGY FROM ANY CULTURE WILL DO. GRANT THE JINN OF THE MIDDLE EAST, THE RAKSHASAS, ASURAS OF HINDUISM, THE DRUIDS AND FAIRIES AND A TRANSFORMATION TO THIS ILLUSORY WORLD WORKS WONDERS. JUST LIKE THE FOURIER TRANSFORM AND LAPLACE TRANSFORM. WHEN THE MATHEMATICS OF COMPUTATION HAS TO BE EXPLAINED TO MILLIONS OF ORDINARY PEOPLE THIS CAN BE EXCUSED. OUR TARGET AUDIENCE IS THE MASS OF SOFTWARE PERSONNEL INVOLVED IN OUTSOURCING.
JUST MODEL THE CAPABILITY OF A STUDENT BY A RECURSIVE FUNCTION AND A LOT OF COMPUTATIONAL COMPLEXITY IS EVIDENT. THIS MAY NOT BE ACCEPTABLE IN SOME ENVIRONMENTS WHICH HAVE OVERDONE RACISM, BUT IS ACCEPTABLE IN MANY CULTURES.
JUST CONSIDER HOW A ORDER IS PLACED WITH THE WAITER/STEWARD IS AN EATING HOUSE WITH A LARGE MENU AND WE CAN MODEL IT BY GENERATORS AND ACCEPTORS.
A MAJOR APPLICATION OF AUTOMATA AND FORMAL LANGUAGE THEORY IS THE AREA OF CONSTRUCTION OF COMPILERS. THE TENDENCY IS TO MAKE THE SUBJECT SO THEORETICAL THAT UTTER CONFUSION REIGNS IN THE MIND OF THE STUDENT. A COMMON SENSE TREATMENT OF THE SUBJECT IS BASED ON THE HISTORIC TEXT "COMPILER CONSTRUCTIONS FOR DIGITAL COMPUTERS". THE ALGORITHMIC ADVANCES IN THE AREA LEND THEMSELVES TO COMMON SENSE EXPLANATIONS. A STILL MORE COMMON SENSE AND USER FRIENDLY APPROACH IS TO USE THE RAILWAY SHUNTING YARD ALGORITHM AS A PROLOGUE TO SYNTAX DIRECTED COMPILERS.THE STANDARD DRAGON BOOK HAS BEEN ATTEMPTED ONLY IN THE THIRD PASS THROUGH THE COURSE.
A DIFFICULT LEGENDARY PROOF IS THE ONE STUDYING THE COMPLEXITY OF THE UNION FIND ALGORITHM. IF WE CONSIDER A COMMON SENSE INTERPRETATION OF THE PROBLEM THE PROOF SEEMS OBVIOUS. START WITH THE 4 BILLION PERSONS ON EARTH AS SINGLETON BUSINESS VENTURES. CONSIDER MERGERS OF BUSINESSES, ORGANISATIONS. THE WEIGHTING RULE SAYS THE SMALLER GANG JOINS THE BIGGER ONE. THE COLLAPSING FIND MODELS EVERYONE IN THE ORGANISATION AS WANTING TO REPORT DIRECTLY TO THE CEO. AS THE SEQUENCE OF UNION FIND OPERATIONS PROCEEDS WE SEE THE BUSINESSES AND ORGANISATIONS UNFOLD AS IN ANY LARGE COUNTRY OR GROUP OF COUNTRIES.THE ENTIRE PROOF LENDS ITSELF TO A NICE QUALITATIVE USER FRIENDLY GRAPHICAL PRESENTATION. SEE HEREpresentations on algorithms.
A DIFFICULT ALGORITHM IS THE ONE RELATED TO KLEENE'S THEOREM. IT IS CLASSIFIED AS DIFFICULT IN MOST STANDARD TEXTS. CHANGE THE SETTING TO THE WORLD OF A CHILD HAVING TO TRAVEL FROM HOME TO CLASS AND WANTING TO KNOW THE PATHS. START WITH DIRECT PATHS AND THEN HAVE THE MUNICIPALITY DEVELOP PARKS TO DIVERT THE CHILD. A DETAILED SIMULATION WITH A THREE NODE GRAPH WITH ALL THE INSTANTANEOUS DESCRIPTIONS MAKES THE THEOREM JUST PLAIN COMMON SENSE. SEE HEREpresentations on algorithms.
THE CHOMSKY HIERARCHY CAN BE EASILY EXPLAINED BY AN ILLUSORY EXAMPLE. THIS USES SPACE COMPLEXITY AS THE BACKGROUND. TYPE 0 LANGUAGES CAN BE LIKENED TO AN ESSAY ORIENTED EXAMINATION WITH UNLIMITED TIME AND ANSWER SCRIPTS. FOR UNLIMTED PAPER USE THE MODEL OF GROWING AUTOMATA. LIMITING TIME AND IN A WAY SPACE CAN YIELD THE RECURSIVE FUNCTIONS.TYPE 1 LANGUAGES CAN BE MODELED BY OBJECTIVE TYPE EXAMINATIONS LIKE GRE AND TOEFL WITH ONE SHEET OF PAPER. THE DIFFICULTY OF THE CLASSIC PROBLEM OF CLOSURE OF CSLS UNDER COMPLEMENT BECOMES INTUITIVELY OBVIOUS. THE TYPE 3 LANGUAGES ARE A MODEL FOR ORAL EXAMINATIONS, WITH THE INK BEING CONFISCATED FROM THE TURING MACHINE. THE TYPE 2 LANGUAGES CAN BE CONSIDERED TO BE A MODEL OF THE PROTOCOL REQUIREMENTS OF VARIOUS LEVELS OF GUESTS AT A FORMAL FUNCTION WITH AN AUDITOR THROWN IN. EVERY CONTEXT FREE LANGUAGE IS THE INTERSECTION OF A DYCK LANGUAGE AND A REGULAR SET(roughly speaking). SEE HEREpresentations on algorithms.
AS ANY COMPUTATION CAN BE CONSIDERED TO BE A MODEL FOR SIMULATING ANY OTHER COMPUTATION, ANY INTERPRETATION OF A COMPUTATION CAN BE TAKEN. WE CHOOSE THE INTERPRETATIONS WHICH ARE COMMONSENSE FOR A PARTICULAR AUDIENCE. THE MAIN DIFFICULTY IS THAT THE INTERPRETATIONS ARE NOT REUSABLE. WHAT IS VALID FOR ONE AUDIENCE MAY BE OFFENSIVE TO ANOTHER AUDIENCE. EXAMPLES DRAWN FROM ILLUSORY WORLD OF POPULAR CARTOON CHARACTERS AND THE WORLD OF CHILDREN ARE SAFEST. IF THE POPULAR CARTOON CHARACTERS ARE COPYRIGHT AND PATENTED THEN ONE CAN USE THE FABLES, FOLKLORE IN A LOCAL OR GLOBAL CONTEXT. SOMETIMES THE STANDARD CARICATURES OF POLITICIANS, GOONS, GOOD AND BAD CHARACTERS ALSO ALLOW USER FRIENDLY, COMMON SENSE EXPLANATIONS. THE ANIMAL WORLD IS RICH PROVIDING SEMANTCS FOR MANY CONCEPTS AND CONSTRUCTS. SEE HEREpresentations on algorithms.
A TOOL THAT HAS PROVED ITSELF TO BE USEFUL IS TO CONVERT THE CONSTRUCTIONS OF GRAMMARS AND AUTOMATA TO DETAILED POWER POINT PRESENTATIONS. THE DETAIL HAS TO BE IN EXCRUCIATING DETAIL. THIS INVOLVES HUNDREDS TO A THOUSAND SLIDES PER PRESENTATION, AKIN TO THE CLASSIC DISNEY CARTOON MOVIES.SEE HEREpresentations on algorithms.
THE PROOF OF THE PUDDING IS IN THE EATING
THE PRESENTATIONS HAD TO BE HIGHLY GRAPHICAL, VERY COLORFUL AND USE SEMANTICS FOR THE SYMBOLS USED. A MAJOR USE OF SYMBOLS IS PRESENT IN AUTOMATA THEORY AND FORMAL LANGUAGES. IT IS NECESSARY THAT THE ABSTRACTION PRESENT IN THE SYMBOLS BE DILUTED BY INTERPRETATION. THIS IS AKIN TO THE USE OF SEMANTICS ASSOCIATED WITH SYMBOLS IN SYNTAX DIRECTED TRANSLATION, THE TRANSITION FROM HTML TO XML OR THE USE OF SEMANTICS AND ATTRIBUTES IN CONSTRAINT DATA BASES. THE USE OF THIS SEMANTICS IS LIKE THE USE OF A CATALYST IN CHEMICAL REACTIONS. THE SEMANTICS IS BASED UPON AN INTERPRETATION OF THE PROBLEM INVOLVED.
IN THE CASE OF A DFA OR NFA ONE CAN USE THEM AS MODELS FOR THE BEHAVIOUR OF A CHILD. THE CHILD CAN BE IN THE PARK, HOME OR CLASS. THE TRANSITIONS CAN BE ON A GOOD MOOD OR BAD MOOD. SUCH A MODEL IS UNIVERSAL, FREE FROM STEPPING ON ANY CULTURAL TOES.
THE TRANSITION ON THE EMPTY STRING IN A FA CAN BE LIKENED TO A HITCHHIKERS FREE RIDE.A TRUE SYMBOL IS WHERE PAYMENT IS REQUIRED FOR THE RIDE. THE CLOSURE ON THE EMPTY STRING TURNS OUT TO BE THE HITCHHIKERS WORLD. SUCH A INTERPRETATION ALLOWS THE SYMBOLS USED IN THE REPRESENTATION TO HAVE SEMANTICS ASSOCIATED WITH THEM. THE SEMANTICS CAN BE VERBALISED OR CAN JUST BE THE UNSAID, UNVERBALISABLE ASSOCIATIONS IN THE CULTURAL ENVIRONMENT.
THE CLASSIC MINIMISATION OF FINITE AUTOMATA BY THE PARTITIONING ALGORITHM CAN BE MODELED AS SIMULATING CLOSELY THE BREAKUP OF THE JOINT FAMILY SYSTEM IN INDIA AS A RESULT OF THE INDUSTRIAL AND INFORMATION REVOLUTIONS.
INTERPRETATIONS FROM SOCIAL NETWORKING MAKE THE SEEMINGLY CLEVER, COMPLICATED PROOFS AND CONSTRUCTIONS OF REDUCTION AMONG A LARGE CLASS OF COMBINATORIAL PROBLEMS SEEM OBVIOUS AND BASED ON COMMON SENSE.
SOME SORT OF A SILVER BULLET IS NEEDED FOR THE EXPLANATIONS DEALING WITH PUSH DOWN AUTOMATA AND TURING MACHINES. FOR THIS PURPOSE THE METHOD FOLLOWED DECADES AGO IN DABSE ON PCS IS USEFUL. THERE A QUERY BY EXAMPLE FOR USED. THE SAME TECHNIQUE CAN BE FOLLOWED FOR PDAS AND TMS.
FOR CFGS, CFL, DCFLS, LR(K) GRAMMARS, PDA, DPDA, DERIVATIONS, AMBIGUITY ETC ETC IT TURNS OUT A SINGLE EXAMPLE SUFFICES TO INTRODUCE THE CONCEPTS. CONSIDER A GRAMMAR FOR EXPRESSIONS IN A PROGRAMMING LANGUAGE LIKE C. THE GRAMMAR ONLY DEALS WITH IDENTIFIERS AS SINGLE SYMBOLS AND USE THE ADDITION OPERATOR ONLY. CARE IS TAKEN REGARDING THE EOF SYMBOL. A DIRECT CONSTRUCTION FOR A LR(0) PARSER FOR A SUITABLE GRAMMAR IS CONSIDERED IN DETAIL. THE INSTANTANEOUS DESCRIPTIONS OF THE PARSER ARE CONSIDERED IN EXCRUCIATING DETAIL. THIS IS REPEATED WITH THE DPDA SHOWN AS A DPDA IN THE DIAGRAMS OF THE INSTANTANEOUS DESCRIPTIONS.
THE PALINDROME LANGUAGE WHICH IS SO CENTRAL TO CFLS AND PDAS HAS A PLETHORA OF INTERPRETATIONS WHICH ARE OBVIOUS AND USER FRIENDLY IN ANY ENVIRONMENT.
THE MODIFICATIONS OF THE TURING MACHINE LENDS ITSELF TO MANY MODELS WHICH TURN OUT TO BE LABORIOUS TO CONSTRUCT. INTUITIVE EXPLANATIONS ARE NORMALLY USED. THIS DOES NOT HELP. WHAT WAS TAKEN WAS A SIMPLE LANGUAGE OF N A'S FOLLOWED BY N B'S. FOR THIS A DETAILED CONSTRUCTION WAS DONE BY OBTAINING THE INSTANTANEOUS DESCRIPTIONS FOR BLANK TAPE, MULTITAPE, TWO DIMENSIONAL, TWO PUSHDOWN TAPE, FOUR COUNTER AND TWO COUNTER MACHINES. SUCH A DEMONSTRATION BY EXAMPLE SEEMS NECESSARY.
A SIMILAR DETAILED SIMULATION BY IDS IS WARRANTED FOR COOK'S THEOREM. TWO STANDARD MODELS ARE USED. ONE DEALS WITH THE RASP MODEL. WE CAN TAKE FOUR BIT MACHINES. A PROGRAM COMPARES TWO VARIABLES AND BASED ON THE RESULT INCREMENTS ONE OF THE VARIABLES NONDETERMINISTICALLY. THE ENTIRE CONSTRUCTION FOLLOWED IN COOK'S THEOREM IS SIMULATED STEP BY STEP IN A POWER POINT PRESENTATION PREPARED IN ABOUT 60 HOURS TIME. THE OTHER METHOD USED IS TO USE A NDTM WITH ONLY ONE CELL WITH A SYMBOL, TWO STATES. AN INTERPRETATION CAN EASILY BE FOUND WHICH IS USER FRIENDLY. THE CONSTRUCTION IS SIMULATED IN DETAIL.
FOR UNDECIDABILITY THE FAMOUS THEOREM THAT THE COMPUTATIONS OF A TURING MACHINE CAN BE SIMULATED BY THE INTERSECTION OF TWO CFLS IS USED. THE PDAS INVOLVED CAN BE SIMULATED BY THE EXACT COVER PROBLEM. ACTUALLY WHAT IS USED IS A MODIFICATION OF THE EXACT COVER PROBLEM. WE CALL IT THE HYBRID COVER PROBLEM. IT IS A CROSS BETWEEN THE SET COVER PROBLEM AND EXACT COVER PROBLEM AND DRAWS SOME IDEAS FROM CONSTRAINT DATA BASES. IT CAN HOWEVER BE REDUCED TO THE EXACT COVER PROBLEM.
PCP CAN VISUALLY AND GRAPHICALLY BE REPRESENTED IN OUR HYBRID COVER PROBLEM. THIS ALLOWS SOME MORE RESULTS FROM UNDECIDABILITY.
THE LONG UBIQUITOUS TRAINS AND RAILWAY STATIONS IN INDIA ARE A RICH SOURCE FOR COMMON SENSE EXPLANATIONS OF MANY PROBLEMS, CONSTRUCTIONS AND PROOFS. THE PROBLEM OF DOVETAILING CAN BE LIKENED TO RECEIVING A RELATIVE IN SOME TRAIN. WITH THE CONSTRAINTS BEING VERY LONG TRAINS AND A VERY LARGE NUMBER OF PLATFORMS. THE ADVENT OF DIESEL AND ELECTRIC LOCOMOTIVES DO NOT MAKE THE SHUNTING YARDS VISIBLE NOWADAYS.
ONE OF THE REQUIREMENTS IS THAT ABOUT 20 FORMAL LANGUAGES HAVE TO BE CLASSIFIED. THIS CAN BE AUGMENTED BY ANOTHER 20. THE CLASSIFICATION IS TO BE DONE AS PER THE CHOMSKY HIERARCHY. TWO METHODS USED ARE THE CONSTRUCTION OF AUTOMATA AND THE USE OF THE PUMPING LEMMA.
EXPLAINING THE PUMPING LEMMA HAS THE DIFFICULTY OF HAVING TO DISTINGUISH BETWEEN NECESSARY CONDITIONS VERSUS NECESSARY AND SUFFICIENT CONDITIONS.
THE LEVELS OF THE PUMPING LEMMA: THE WEAK FORM, THE MEDIUM FORM AND THE STRONG FORM, CAN BE LIKENED TO THE SECURITY CHECKS OF DIFFERENT LEVELS FOR A TERRORIST. ALTERNATIVELY THEY CAN REPRESENT THE DIFFERENT LEVELS OF INSPECTION OF A AN ACADEMIC, INDUSTRIAL, GOVERNMENT OR MILITARY ORGANIZATION BY SOME STATUTORY BODY.
THE LONG STRING USED IN THE APPLICATION OF THE PUMPING LEMMA CAN BE LIKENED TO A LONG TRAIN. THE PROOFS ARE BEST EXPLAINED BY HAVING ONE OR TWO SLIDING WINDOWS MOVE OVER THE ENTIRE STRING.
THE NORMAL TENDENCY OF TEXT BOOKS IS TO TREAT ONE OR TWO SCORE STANDARD FORMA LANGUAGES OF INTEREST AS CONSISTING OF DRY SYMBOLS. COMMON SENSE EXPLANATIONS DEMAND THE SYMBOLS BE GIVEN SOME ATTRIBUTES OR SEMANTICS. IN ANY NATURAL LANGUAGE WHEN THE ALPHABET IS EXPLAINED TO A CHILD A CHART IS USED FOR THIS PURPOSE. IN ENGLISH WE HAVE—A.SEMANTICS=”APPLE” AND SO ON TILL Z.SEMANTICS=”ZEBRA”. IN THE INTERPRETATION OF FORMAL LANGUAGES WE HAVE FOUND IT USEFUL TO HAVE FORMAL LANGUAGES AS REPRESENTING THE TRAVELS OF SOME MASCOT EMPLOYED FOR THE SYLLABUS. HERE WE HAVE---A.SEMANTICS=AUTO/AIRPLANE RIDE, B.SEMANTICS=BUS/BOAT RIDE, C.SEMANTICS=CAR RIDE, D.SEMANTICS=DONKEY RIDE/DRUDGE WALKING. SIMILAR INTERPRETATIONS ARE GIVEN THE A BINARY OR TERNARY ALPHABET.
THE PROOF OF THE PUDDING IS IN THE EATING
PALINDROMES ARE PERHAPS A BETTER COMMONSENSE EXPLANATION OF THE LAST THREE. THE ORDER OF ARRIVAL CAN BE RELATED TO PROTOCOLS TO BE FOLLOWED FOR GUESTS AT A FORMAL FUNCTION. THIS AUGMENTED BY FINITE AUTOMATA ALLOWS USER FRIENDLY CONSTRUCTIONS OF SOME AUTOMATA.
TO THE ABOVE LIST COULD BE ADDED, WITH SUITABLE INTERPRETATIONS----
22) THE UNION OF SOME OF THE ABOVE LANGUAGES.
23) THE INTERSECTION OF SOME OF THE ABOVE LANGUAGES
24) THE COMPLEMENT OF THE ABOVE LANGUAGES.
25) THE COMBINATIONS OF UNION, INTERSECTION AND COMPLEMENT OF SOME OF THE ABOVE LANGUAGES.
26) EXTENSIONS TO SOME OPERATIONS ON LANGUAGES. COMMON SENSE EXPLANATIONS FOR THE OPERATIONS USED.
A CLASSIC COMPILATION OF INTRACTABLE PROBLEMS BY SOME EXPERTS HAS AN INTERESTING COMMENT. IN THEIR EXPOSITION OF REDUCABILITY AMONG COMBINATORIAL PROBLEMS THEY SAY THEY HAVE FOUND IT EASIER TO DEVELOP THEIR OWN PROOFS RATHER THAN UNDERSTANDING THE PUBLISHED PROOF. THIS SHOWS THAT THE USE OF FORMALISM HAS BEEN OVERDONE. THE SYMBOLS AND FORMALISM ARE STATIC, AND THEY SHOULD PREFERABLY DENOTE SOME SEMANTICS BY SOME COMMONSENSE INTERPRETATION.
WHEN THE COMPUTATION OF ANY COMPUTATIONAL DEVICE CAN BE DESCRIBED BY A SEQUENCE INSTANTANEOUS DESCRIPTIONS WE CAN USE THE EXACT COVER OR HYBRID COVER PROBLEM TO MODEL THE SAME. THE ONLY CONSTRAINT BEING THAT ONLY A FINITE PORTION OF ONE ID BE CHANGED INTO A FINITE PORTION OF THE SUCCEEDING ID. THIS OCCURS IN TURING MACHINE COMPUTATIONS, RAM AND RASP COMPUTATIONS, COMPUTATION MODELED BY FORMAL GRAMMARS ETC. ETC. ONE CAN FURTHER DESCRIBE THESE BY SAYING THE VALID COMPUTATIONS ARE DESCRIBED BY THE INTERSECTION OF TWO CONTEXT FREE LANGUAGES. THIS ALLOWS A LOT OF UNDECIDABILITY RESULTS TO BE DESCRIBED VISUALLY IN A USER FRIENDLY MANNER.
ALL ALGORITHMS OVER THE LAST HALF A CENTURY HAVE BEEN STUDIED WITH STATIC INPUT DATA. DYNAMICALLY VARYING DATA IS CALLED FOR IN EXPOSITIONS OF THE CONCEPTS OF THE THEORY OF COMPUTATION. A STATIC TABLE FOR THE EXACT COVER PROBLEM CAN MODEL THE RECURSIVE FUNCTIONS, FOR THE R.E. SETS A DYNAMICALLY GROWING OR VARYING TABLE IS IN ORDER. THIS IS MERELY A WATERED DOWN APPLICATION OF CONSTRAINT DATA BASES.
A LOT OF REDUCTIONS AMONG COMBINATORIAL PROBLEMS CAN BE MADE SIMPLER BY USING THE HYBRID COVER PROBLEM AS AN INTERMEDIATE STAGE. THE MAPPING OF A NDTM COMPUTATION DIRECTLY TO THE NP-COMPLETE PROBLEM CAN BE CONSIDERED.
HOWEVER A FUNDAMENTAL RULE FOLLOWED IS THAT THE AIM IS NOT TO REWRITE OR CHANGE THE STANDARD CLASSIC TEXTS. THE METHODS, PROOFS AND CONCEPTS FOLLOWED THERE ARE TO BE EXPLAINED. THE CLASSIC TEXTS ARE TO BE TREATED AS THE HOLY WRIT.
You will find hints & solutions to GATE problems in the Theory of Computation, in the web addresses given below. They year relates to the GATE question paper under consideration.
Do not look up the solution unless you are desperate.
| ANS | ||
| 1987 | 1988 | 1989 |
| 1990 | 1991 | 1992 |
| 1993 | 1994 | 1995 |
| 1997 | 1998 | 1999 |
| 2000 | 2001 | 2002 |
| 2003 | 2004 | 1987 |
| QUES | ||
| 1987 | 1988 | 1989 |
| 1990 | 1991 | 1992 |
| 1993 | 1994 | 1995 |
| 1997 | 1998 | 1999 |
| 2000 | 2001 | 2002 |
| 2003 | 2004 | 2005 |
| 2006 | 2007 | 2008 |
The same links are given below directly in case you want the URL
http://www.gateguru.org/automata/gate_1987_toc_solutions.htm
http://www.gateguru.org/automata/gate_1988_toc_solutions.htm
http://www.gateguru.org/automata/gate_1989_toc_solutions.htm
http://www.gateguru.org/automata/gate_1990_toc_solutions.htm
http://www.gateguru.org/automata/gate_1991_toc_solutions.htm
http://www.gateguru.org/automata/gate_1992_toc_solutions.htm
http://www.gateguru.org/automata/gate_1993_toc_solutions.htm
http://www.gateguru.org/automata/gate_1994_toc_solutions.htm
http://www.gateguru.org/automata/gate_1995_toc_solutions.htm
http://www.gateguru.org/automata/gate_1996_toc_solutions.htm
http://www.gateguru.org/automata/gate_1997_toc_solutions.htm
http://www.gateguru.org/automata/gate_1998_toc_solutions.htm
http://www.gateguru.org/automata/gate_1999_toc_solutions.htm
http://www.gateguru.org/automata/gate_2000_toc_solutions.htm
http://www.gateguru.org/automata/gate_2001_toc_solutions.htm
http://www.gateguru.org/automata/gate_2002_toc_solutions.htm
http://www.gateguru.org/automata/gate_2003_toc_solutions.htm
http://www.gateguru.org/automata/gate_2004_toc_solutions.htm
http://www.gateguru.org/automata/gate_2005_toc_solutions.htm
http://www.gateguru.org/automata/gate_2006_toc_solutions.htm
http://www.gateguru.org/automata/gate_2007_toc_solutions.htm
http://www.gateguru.org/automata/gate_2008_toc_solutions.htm
http://www.gateguru.org/automata/gate_2009_toc_solutions.htm
http://www.gateguru.org/automata/gate_2010_toc_solutions.htm
http://www.gateguru.org/automata/gate_2011_toc_solutions.htm
http://www.gateguru.org/automata/gate_2012_toc_solutions.htm
The question papers will be in the links given below
YOU ARE FREE TO SEND YOUR COMMENTS AND INQUIRES TO
godel_turing_society@yahoo.com
goedel_turing_society@yahoo.com
THE ABOVE MATERIAL IS PREPARED BY THE GOEDEL TURING SOCIETY OF INDIA
THERE MAY BE ERRORS, WHICH WILL BE CORRECTED AS YOU INTERACT WITH YOUR COMMENTS
| ANS | ||
| 1987 | 1988 | 1989 |
| 1990 | 1991 | 1992 |
| 1993 | 1994 | 1995 |
| 1997 | 1998 | 1999 |
| 2000 | 2001 | 2002 |
| 2003 | 2004 | 1987 |
| QUES | ||
| 1987 | 1988 | 1989 |
| 1990 | 1991 | 1992 |
| 1993 | 1994 | 1995 |
| 1997 | 1998 | 1999 |
| 2000 | 2001 | 2002 |
| 2003 | 2004 | 1987 |