Theory of Computation PDF

Theory of Computation Published By: Physics Wallah ISBN: 978-93-94342-39-2 Mobile App: Physics Wallah (Available on Play Store) Website: www.pw.live Email: [email protected] Rights All rights will be reserved by Publisher. No part of...

Theory of Computation Published By: Physics Wallah ISBN: 978-93-94342-39-2 Mobile App: Physics Wallah (Available on Play Store) Website: www.pw.live Email: [email protected] Rights All rights will be reserved by Publisher. No part of this book may be used or reproduced in any manner whatsoever without the written permission from author or publisher. In the interest of student's community: Circulation of soft copy of Book(s) in PDF or other equivalent format(s) through any social media channels, emails, etc. or any other channels through mobiles, laptops or desktop is a criminal offence. Anybody circulating, downloading, storing, soft copy of the book on his device(s) is in breach of Copyright Act. Further Photocopying of this book or any of its material is also illegal. Do not download or forward in case you come across any such soft copy material. Disclaimer A team of PW experts and faculties with an understanding of the subject has worked hard for the books. While the author and publisher have used their best efforts in preparing these books. The content has been checked for accuracy. As the book is intended for educational purposes, the author shall not be responsible for any errors contained in the book. The publication is designed to provide accurate and authoritative information with regard to the subject matter covered. This book and the individual contribution contained in it are protected under copyright by the publisher. (This Module shall only be Used for Educational Purpose.)  Design Against Static Load INDEX 1. Basics of Theory of Computation......................................................................................... 7.1 – 7.5 2. Finite Automata................................................................................................................... 7.6 – 7.21 3. Push Down Automata.......................................................................................................... 7.22 – 7.29 4. Turning Machine................................................................................................................. 7.30 – 7.39 GATE-O-PEDIA COMPUTER SCIENCE & INFORMATION TECHNOLOGY  Design Against Static Load 1 BASICS OF THEORY OF COMPUTATION 1.1 Symbol Symbol represents very unique in the world. Any small thing that never be broken into any other is called as symbol. One Length string Symbol It is smallest one 1.2 Alphabet () It is a set of finite number of symbols. Example: English alphabet = {a, b,... z} Binary alphabet = {0, 1} Decimal alphabet = {0, 1, 2,... 9} We can create our own alphabet = {gate, cs, it, exam} where gate, cs, it, exam all are symbols 1.3 String It is sequence of symbols defined over given alphabet. let  = {a, b} Strings possible are , a, b, aa, bb……… Strings over English Alphabet: deva, gate, exam, etc. Strings over Binary Alphabet: 0010, 1011, 1101, 1111, etc. Strings over Decimal Alphabet: 3012, 2345, 5438, etc. Note: Different length strings over given alphabet I Zero length string Empty string / Null string  or  is used to denote empty string length of empty string. || = 0. II One length string over  = {a, b} are a, and b (2 strings). III Two length strings over  = {a, b} are da, ab, ba, and bb (4 strings). GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.1  Theory of Constraints 1.4 Operations on Strings There are various operations on strings: Unary and Binary operations 1. length of a string: Length of a string is denoted as |w| and is defined as the number of positions for the symbol in the string. Example: w = aba |w| =|aba| = 3 2. Reversal of a string: It will reverse or changes the order of a given string w. Example: w = abb wR = bba 1.4.1 Concatenation of Two Strings Given two strings w1 and w2, we define the concatenation of w1 and w2 to be the string as w1w2. Example: w1 = a, and w2= ba Then w1w2 = a.ba = aba. 1.4.2 Prefix of a String A substring with the sequence of beginning symbols of a given string is called a “prefix”. Example: (i) w = aaaa Prefixes = {, a, aa, aaa, aaaa} (ii) w = abcd Prefixes = {, a, ab, abc, abcd} Note: If |w| = n then |wRev| = n. If length of w1 is n1 and length of w2 is n2 then length of w1w2 = |w1 w2| = n1 + n2. Let w be n length string. (i) Number of prefixes in w = n+1 (ii) Number of non-empty prefixes of w = n (iii) Number of different length prefixes of w = n + 1 (iv) Number of different length prefixes of w excluding zero length = n 1.4.3 Suffix of a String A substring with the sequence of ending symbols of a given string is called a “suffix”. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.2  Theory of Constraints Example: (i) w = aaaa Suffixes = {, a, aa, aaa, aaaa} (ii) w = abcd Suffixes = {, d, cd, bcd, abcd} Note : Let w be n length string. (i) Number of suffixes of w = n + 1 (ii) Number of non-empty suffixes of w = n (iii) Number of different length suffixes of w = n + 1 (iv) Number of different length suffixes of w excluding zero length = n 1.4.4 Substring of a String Let w be n length string. minimum = n +1 (i) Number of substrings of w (over 1 symbol) maximum = 1+ n + (n – 1) +....+1 (all characters distinct) =1 + n = n +1 minimum = n (ii) Number of non-empty substrings of w maximum =n Number of different length substrings of any given n length string =n+1 Number of different length substrings of any given n length string excluding zero length=n. 1.5 Relation between Symbol, Alphabet, String and Language Character Symbol   Character set Alphabet   Token String   C Language Language GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.3  Theory of Constraints 1.5.1 Chomsky Hierarchy Chomsky hierarchy includes all the problems in the world classified into classes.  Type 3 is the smallest class, and Type 0 is the biggest class. Type 3 Type 2 Type 1 Type 0 Language: Regular Context free Context sensitive Recursively Enumerable Automata: Finite Automata Push down Linear Bounded Turing Machine Automata Automata Grammar: Regular Context free Context Sensitive Unrestricted 1.6 Language Language is set of strings defined over alphabet (). Let  = {a,b}. Then  = 0 1 2  ……. = set of all strings = universal language = {, a, b, aa, ab, ba,...}  =   ={a,b}. {a,b} = {aa, ab, ba, bb} 2 1 1 Language: It is a subset of *  L  * A language is a collection of strings that must be a subset of * where * is a universal language. Example: L = ab* = {a, ab, abb,..........} GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.4  Theory of Constraints 1.7 Types of Languages Finite Language Infinite Language Regular language DCFL (Deterministic CFL) CFL CSL Recursive Language Recursive Enumerable Language (REL) 1.8 Types of automata Ralations between these machines:  1. Less power: It can Represent less number of languages. 2. More power: It can Represent more number of languages Compare to all these machines.  GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.5  Theory of Constraints 2 FINITE AUTOMATA 2.1 Introduction Finite Automata describes or represents a regular language. Finite Automata is of two types: (i) Acceptor: Accepts or rejects given string. (ii) Transducer: Produces output string for given input string. Example: 1's complement of binary number: Input = 10100, Output = 01011 2.2 Finite Acceptor (Finite Automata) Finite Automata: FA = (Q, Σ, δ , q 0. F) Set of final states Initial state Transition function Set of input symbols Set of finite number of states GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.6  Theory of Constraints 2.3 Construction of DFA 1. If epsilon belongs to L, then initial state must be final in DFA. 2. Dead state: It is non-final state but it never contain a path to final. Once we reach the dead state, there is no way to reach to the final state. If every state is final then every string accepted in the DFA. 3. If all states are finals in DFA then L(DFA) =  * 4. If every state is non final in a DFA then L(DFA) =  or L(DFA) = {}, L  * L L  L  * LL  If |w| = n or |w|  n, then number of states in minimum DFA = (n + 2) states If |w|  n then number of states in minimum DFA = n+ 1 states. Start condition, exactly, atmost length question requires Dead state but end condition, contain substring, atleast length questions do not require dead state. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.7  Theory of Constraints Over one symbol  = {a}. Length of string is equal to number of a's in string. |w|= na(w). Let L={w|w  {a,b}*, na(w) is divisible by m, nb(w) is divisible by n}. Then Number of states in DFA= m×n. Let L={w | w belongs to {a. b}*, nth symbol of w from begin is 'a'}. Then Number of states in DFA = (n + 2). Number of equivalence classes for any regular set L = Number of states in minimal DFA that accepts L. 2.4 Non-Deterministic Finite Automata 2.4.1 Introduction Finite Automata can be designed in two ways: Finite Automata DFA NFA (NDFA) without with - moves - moves All these finite state machines are equivalent. DFA . NFA We can convert one finite state machine to any other finite state machine. For every gular language, we can design infinite equivaent DFAs or infinite equivalent NFAs but minimum DFA is uique for given regular language. For every regular language, one or more minimum NFAs may exist. Note : For every regular language: (i) Unique minimum DFA exists. (ii) One or more minimum NFAs exists. 2.5 Comparison of NFA and DFA |w| = n |w|  n |w|  n Number of states in n+1 n+1 n+1 NFA Number of states in n+2 n+2 n+1 DFA If every string has nth symbol from begin is 'a' over binary alphabet {a, b} then (n + 1) states in minimum NFA but (n+2) states in minimum DFA. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.8  Theory of Constraints If every string has nth symbol from end is 'a' over binary alphabet {a, b} then 2n states in minimum DFA and (n + 1) states in minimum NFA. 2.5.1 COMPARISON OF DFA AND NFA (NFA vs DFA) NFA DFA (1) Transition Function (  ) Q ×  → 2Q Q× → Q (2) Number of paths for string For valid string: 1 path For valid string: 1 path For invalid string: >=0 paths For invalid string: 1 path 2.5.2 Number of states in DFA and NFA for Regular Languages Language NFA states DFA states (1) {w | w  {a, b}*, |w| = n} n+1 n+2 (2) {w | w  {a, b}*, |w|  n} n+1 n+2 (3) {w | w  {a, b}*, |w|  n} n+1 n+2 (4) {w |w  {a, b}*, w starts with a} 2 3 (5) {w| w {a, b}*, nth symbol from begin is a} n+1 n+2 (6) {w| w  {a, b}*, nth symbol from end is 'a'} n+1 2n 2.5.3 Finding number of states in DFA using NFA NFA (n states)  Subset Construction DFA (2n sates exists)  Partition algorithm Minimum DFA ( 2n states) atmost 2n states Every DFA is NFA, but NFA need not be DFA. 2.5.4 Relation between NFA with epsilon, NFA without epsilon, and DFA GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.9  Theory of Constraints 2.6 Regular language Representation Regular Language FA Regular Expression Regular Grammar DFA NFA without with moves moves 2.7 FA Classification 2.8 Moore machine and mealy machine Moore machine Mealy machine Transition Function  : Q × Q  : Q × Q Output Function  : Q   : Q ×  Outpput is asociated with every state. Output is associated with transition. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.10  Theory of Constraints 2.8.1 Example for Moore machine and Mealy machine Moore Mealy Q = {A, B}  = {0, 1}  = {x, y} Q = {A, B} Outpput is asociated with state.  = {0, 1}  = {x, y} Output is associated with transition. No extra output is produced. Extra one output is produced other than desired For 3 length input, we are getting the 3 length output. output. So, we can ignore this extra output as this is the machine property. 2.9 Difference between Moore machine and Mealy machine Moore machine Mealy machine 1.  Q × Q Q × Q  Q  Q ×  2. 3. Length of O/p If n length I/P (assume 1 length O/P If n length input (assume 1 length symbol is taken at each state) then O/P symbol is taken at each O/P length is (n+1). transition) is given then O/P length is n. 4. By default DFA no final state. DFA no final state. 2.10 Constuction of FA with output Moore Machine  Mealy Machine GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.11  Theory of Constraints Note : For every problem, if moore machine exists the we can also construct equivalent mealy machine. Example: Sum of present bit and previous bit. Mealy Machine 0/00 0/01 1/10 1/01 Previous bit ‘0’ Previous bit ‘1’ Moore Machine  Bzoth are equivalent 2.11 ClassificationMealy of Finite Machine State Machine (FSM) 2.12 Regular Expression Definition: o Regular expression represents a regular language. o It describes a regular set. o L (regular expression) is regular set. o It is a kind of declarative way to represents a regular language. o Regular expression generates a regular set. o It uses 4 operators to represent a regular language. Regular Expression Operators Operandas (Regular expression) Unary Binary GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.12  Theory of Constraints 2.13 Operators of Regular Expression 1. OR (  )   Binary Operator 2. Concatenation(.)  3. Kleenestar ( *)   Unary Operator 4. Kleenestar (+)  Regular Expression Equivalent Regular Set a+b L(a + b) = {a, b} a+a=a L(a + a) = {a} a+=a L(a + ) = {a} a+= +a L(a + ) = {a, } += L(+) = {} +=ϕ L( + ) = {} a  b = ab L (a  b) = {ab} a=a L (a  ) = {a} = L() = {} =ϕ L(  ) = {} a  a = aa = a2 L (a  a) = aa = {a2} 2.14 Kleene star/ kleene closure / closure R* ( Kleene closure of R): R* = R° +R1+ R2 +R3 + … =  + R + RR + RRR+ …. Example: a* = {a0, a1, a2, a3 ,...} = {, a , aa, aaa, …} = Set of all strings over a. * = 0 + 1 + 2 + 3 + …. =  +  +  +  + …. =  +  =  2.15 Positive Closure (Kleeme Plus) R+ (Positive Closure of R): R+= R1 + R2 + R3 + ….. R* = R 0 i.e. repeart R any number of time R+ = R1 i.e. repeat R atleast 1 time. R* = R+ + R0 Example: (1) a + = {a, aa, aaa, …} = {an | n  1} (2) + =  = * (3) + =  GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.13  Theory of Constraints Properties : OR Concatenation 1. Identity   2. Associative Yes Yes 3. Commutative Yes No 4. Annihilatior *  2.16 Identification of Regular Languages 1. L={anbm |n, m  0} = a*b* (Regular language) 2. L= {anbm|m 10} (Non Regular language) 4. L= {anbm |m = n, m < 10} (Regular language) 5. L={ anbm |m = n, m > 10} (Non Regular language) 6. L={ambn | gcd (m, n) = 1} (Non Regular language) 7. L={ambn |LCM (m, n) = 1} (Regular language) 8. L= {anbn | n >= 0} (Non Regular language) 9. L={anb2n |n  0} (Non Regular language) 10. L={ambn | m=even, n =odd} (Regular language) 11. L={ambn | m = n = even} (Non Regular language) OR L = {a2nb2n | n = even} 12. L={a*} over = {a} = Regular language 13. L={a2n | n >= 0} over  = {a}. L= a2n=(aa)* = Regular language GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.14  Theory of Constraints 14. L= {aPrime} over  = {a} = Non regular language 2 15. L={ a n | n  0} over  = {a} L={epsilon, a, aaaa, a9, a16...}, FA Not possible for L. So, it's Non-Regular language. n 16. L= { a 2 | n > 0}over  = {a} Non Regular language n 17. L= { a 2 | n  10} = Regular language 18. L={an! | n  100} over S = {a} = Non Regular language n 19. L={ a n |n  10} over  = {a} = Non Regular language 20. L = {aPrime}* over  ={a} L = complement of {a} = *– {a} ={, a2, a3 a4 ,a5, a6, a7,...}= Regular language 21. L = {aprime | prime n } DCFL L = { ambnc* c  n } DCFL L = { ambnc* m  n } DCFL L = { ambncm+n m, n  0 } is DCFL GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.28  Theory of Constraints L = { am+nbn+kck+m m, n  0 } is CFL L = { wwr w belongs to {a, b}* } is CFL but not DCFL  GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.29  Theory of Constraints 4 4.1 Classification of Languages TURNING MACHINE 1. All languages which are not RELs 2. All not recursive languages 3. All not CSLs 4. All not CFLs 5. All not DCFLs 6. All not regulars 7. All recursive languages which are not DCFLs 8. All RELs which are not DCFLs 4.2 There are Two types of TM (a) DTM (Deterministic TM) (b) NTM (Non- Deterministic TM) DTM      :QQ  L , R     Left Right   NTM  : Q   2Q{ L, R} GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.30  Theory of Constraints 4.3 Unrestricted Grammar (UG) and Context Sensitive Grammar (CSG) Unrestricted grammar (UG) also called as  RE grammar  Phase structure grammar Context sensitive grammar (CSG) is also called as  Non contracting grammar  Bound restricted grammar 4.4 Grammars Left Linear Grammar (LLG): V VT*  T* Right Linear Grammar (RLG): V T*V  T* Linear Grammar (LG): V T*VT*  T* Context Free Grammar (CFG): LHS RHS, LHS  RHS Unrestricted Grammar (UG): LHS RHS 4.5 Equivalence of various TMs TM  Single tape TM TM  One-way infinite tape TM TM  Two-way infinite tape TM TM  Multi tape and multi head TM TM  Universal TM TM  Two stack PDA TM  Multi stack PDA TM  FA with two stacks TM  FA + R/W tape + Bidirectional head 4.6 Restrictions on TM (1) If TM tape is read only tape, this TM accepts regular. TM  FA (TM with read only tape) (2) If TM head is unidirectional then L(TM) = Regular. (3) If TM tape is read only and unidirectional head then L(TM) = Regular. (4) If TM always halts then L(TM) is recursive language. (5) If TM always halts and uses linear bound tape then L(TM) is CSL. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.31  Theory of Constraints 4.7 LBA, HTM and TM HTM: It is a TM that always halts for every input. TM: It halts for every valid string and for invalid strings either halts at “non final state” or “never halts”. LBA: It is HTM but length of the tape we use linearly bounded.  LBA accepts CSL languages.  HTM accepts recursive languages.  TM accepts Recursive Enumerable (RE) languages. 4.8 Recursively Enumerable Language It is also called as:  Enumerable language  TM recognizable language  TM Enumerable language  Partially decidable language  Semi-decidable language 4.9 Recursive Language  Recursive language is acceptable by HTM, and hence acceptable by TM.  Recursive also called as decidable language.  Recursive also called as Turing decidable language. If TM always halts, then TM is called as HTM. 4.10 Difference between Recursive and REL  All Recursive languages are RE languages. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.32  Theory of Constraints Note : 1. Union: REL  Finite  REL REL  Regular  REL REL  CFL  REL REL  Recursive  REL REL1  REL2  REL 2. Intersection: REL  Finite  REL (Finite) REL  CFL  REL REL  Rec  REL REL1  REL2  REL 4.11 Closure Properties of Recursive languages I. The following operations are not closed for recursive languages:  Subset  Substitution  Homomorphism  Finite substitution  Infinite union  Infinite intersection  Infinite concatenation  Infinite difference  Infinite substitution II. The following operations are closed for recursive languages:  Complement  Difference  Finite difference  Infinite followed by , , -, , , f  Remember not closed operations 4.12 Complement of Recursive Vs Complement of REL GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.33  Theory of Constraints  Complement of Recursive set is Recursive.  Complement of REL is either Recursive or non-REL.  Complement of REL never be “REL which is not recursive”. 4.13 Decidable and Undecidable 4.14 Decidable Vs Undecidable, RE Vs Not RE, Countable Vs Uncountable Decidable and Undecidable HTM exist HTM not exist (Rec language) (not Rec language) RE and Not RE TM exist TM not exist Countable set and Uncountable set X is countable set (X is not countable set) iff Xf(X) is bijective where f(X) is known countable set. GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.34  Theory of Constraints Note :  If problem p is decidable then p is also decidable.  If problem p is Undecidable then p is also UD.  If problem p is RE but not recursive then p is not RE.  If problem p is not RE then p is either “Not RE” or “RE but not Recursive”. 4.15 Decision Properties Table  D: Decidable  UD: Undecidable FA DPDA PDA LBA/HTM TM H (Halting) D D D D UD M D D D D UD (Membership) Em D D D UD UD (Emptiness) F (Finiteness) D D D UD UD GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.35  Theory of Constraints T (Totality) D D UD UD UD Eq D D UD UD UD (Equivalence) D (Disjoint) D UD UD UD UD S (Set D UD UD UD UD Containment) 4.16 Decidable problem for DFA / NFA/ FA/ Regular (1) Halting problem for FA / Reg/ DFA / NFA is decidable. (2) Non-halting problem for FA / Reg/ DFA / NFA is decidable. (3) Membership problem for FA / Reg/ DFA / NFA is decidable. (4) Non-membership problem for FA / Reg/ DFA / NFA is decidable. (5) Emptiness for FA / Reg/ DFA / NFA is decidable. (6) Non-emptiness problem for FA / Reg/ DFA / NFA is decidable. (7) Fitness problem for FA / Reg/ DFA / NFA is decidable. (8) Non-fitness problem for FA / Reg/ DFA / NFA is decidable. (9) Totality problem for FA / Reg/ DFA / NFA is decidable. (10) Non-totality problem for FA / Reg/ DFA / NFA is decidable. (11) Equivalence problem for FA / Reg/ DFA / NFA is decidable. (12) Non-equivalence problem for FA / Reg/ DFA / NFA is decidable. (13) Disjointness problem is decidable for FA / Reg/ DFA / NFA. (14) N0n-disjointness problem is decidable for FA / Reg/ DFA / NFA. (15) Set containment problem for FA / Reg/ DFA / NFA is decidable (16) Non-set containment problem for FA / Reg/ DFA / NFA is decidable. 4.17 Decidable problems for CFLs/DCFLs GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.36  Theory of Constraints 4.18 Decidability problems for Recursive languages Problems Recursive 1. Halting D 2. Non-Halting D 3. Membership D 4. Non-membership D 5. Emptiness UD [Not REL] 6. Non-emptiness UD [RE but not Rec] [SD but UD] 7. Finiteness UD [Not RE] 8. Non-finiteness UD [Not RE] 9. Totality UD [Not RE] 10. Non-totality UD [RE but not Rec] [SD but UD] 11. Equivalence UD [Not RE] 12. Non-equivalence UD [RE but not Rec] 13. Disjointness UD [Not RE] 14. Non-disjointness UD [RE but not Rec] 15. Set containment UD [Not RE] 16. Non-set containment UD [RE but not Rec] GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.37  Theory of Constraints 4.19 Classification of Languages based on Decidability All RE languages can be classified into 3 important classes. 4.19.1 Decidability Vs Turing Machine 4.20 Decidable languages (1) Finite set  Decidable (2) ∑ = {a, b}  Decidable (3) ∑  Set of finite number of symbols  Decidable (4) ∑* over alphabet ∑ = {a, b}  Decidable (5) {M  M is DFA, M accepts ab}  Decidable GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.38  Theory of Constraints (6) {TM  Number of states in TM= 2}  Decidable (7) {TM  TM reaches state q within 100 steps}  Decidable (8) { TM  TM accepts REL}  Decidable   GATE WALLAH COMPUTER SCIENCE & INFORMATION TECHNOLOGY HANDBOOK 7.39