# Theory of Computation - GO Classroom

Day  1  2  3 Date Contents Slides Assignments Sep 27 Regular Language- alphabets, language(set of strings), language class or language family All languages -uncountably infinte, set of all languages(Finite, Regular, Context free) are countably infinite, there is an uncountable recursive set of languages outside recursively enumerable languages  Finite Automata- Deterministic Automata and Non Deterministic Automata- mathematical representation Number of DFA's possible with two states over {0,1} What do you know about Regular language? 1.) Finite automata acceptance 2.) Deterministic finite automata acceptance 3.) Has an equivalent regular expression Operators in regular expression, Deterministic and Non Deterministic languages are not same in CFL Pumping Lemma- used to check if a language is not regular Regular set --> Pumping lemma Definition with examples Methods to check if a language is regular: (i) Pumping lemma- one way (ii) Regular expression/ Finite automata/ Regular grammar- two way (iii) Myhill- Nerode theorem- equivalence relation for this theorem, distinguishing string Difference between context-sensitive and recursive language- space complexity is linear in LBA, find an example for language accepted by TM but not LBA Sep 28 Product automata If L is regular: Is L empty? Is L equal to sigma*? Is reverse of L regular? Is first half(L) regular? More examples to check whether grammar is regular or not. Regular Grammar: G=(V, T, P, S) Left linear grammar- only one non-terminal on left of each production Right linear grammar- only one non-terminal on right of each production All linear grammars are not regular, but all regular languages are either left linear or right linear. Context Free Grammar- Pushdown Automata = NFA + Stack L={a^n c b^n | n >= 0} not regular Push all a's into stack, if c is reached do not do anything on stack, now for each b pop an a from stack. If stack is empty finally then string is accepted if the input is over. PDA- mathematical representation, accepts all regular languages Acceptance by final state and acceptance by empty stack- both are eqivalent in case of PDA In Deterministic PDA acceptance by empty stack is a subset of acceptance by final state. Sep 29 Half(L) is regular - how to construct DFA for Half(L) Squareroot(L) is regular Square(L) is not regular Sep 30-Oct 2 Solve GO pdf questions on regular language,regular expressions and context free languages Oct 3 Pushdown Automata Given a PDA which accepts by empty stack, how to convert it to PDA accepts by final state. {aab,aa,a} - Can you make PDA that accept by empty stack? NFA = DFA < DPDA < PDA PDA by empty stack = PDA by final state DPDA by empty stack < DPDA by final state {a,aa,aab}- If strings are prefixes then it cannot be accepted by DPDA by empty stack. Which is more powerful? DFA or DPDA by empty stack These two are not comparable. There are some languages by DPDA empty stack which cannot be accepted by DFA and vice-versa. Language of [DPDA by empty stack] = LR(0) Assignment: Take an input executable and an input 'w' for that and outputs "yes" when the executable finish running. Oct 4 Assignment explanation: FSM, PDA - no chance for infinite loop How to check PDA is going to infinite loop? - we can detect it from PDA configuration Turing Machine Extra power for TM (i) can modify tape (ii) can move left TM can go to infinite loop. Case 1: It always outputs [correct answer]  Decidable , Language is Recursive All problems solved by FSM Case 2: It always outputs "Yes" for "Yes" case Semi-decidable, Language is Recursively Enumerable Halting problem Case 3: It cannot output "Yes" for all "yes" cases Not even semi-decidable, Language is not Recursively Enumerable Complement of Halting problem. Given a TM and a word whether that TM does not stop running? Outputs no for all "no" cases but for all "yes" cases we cannot print "yes". Both case 1 and case 2 are Undecidable Case 4 does not exist ie, it always outputs "no" for all "no" cases(included in case 3) Halting problem is both semi-decidable and undecidable. Complement of Halting problem is not even semi-decidable and it is undecidable. LBA - Linear Bounded Automata The tape space is limited, it is bounded by some multiple of input string. Eg: divisible by 10(it can be any multiple of 10) What about acceptance of empty string in LBA? Empty string is added as special case.(no linear bound for empty string) Not even Recursively Enumerable is largest set of languages. Given a two DFA M , N ,Is L(M)=L(N)? Is L(M) subset L(N)? L(M) ∩ L(N)' = Φ then L(N) AND L(N) ∩ L(N)' = Φ then L(M) = L(N) Given two DPDA's can we say if they are accepting the same language or not?- Decidable(recent study) Checking if CFL is empty?- Decidable Oct 5 Closure properties of language families- Union, intersection, compliment, reverse for Regular, DCFL, CFL, CSL, Recursive, Recursively Enumerable Counter examples for proving not closed L1 and L2 are two DCFL's. Is L1 ∩ L2 a DCFL? - Undecidable(no algorithm to detect this) If L2 is regular then it is decidable(always an Yes) Trivial property - either the property satisfied by all elements of set or none of the elements satisfy that property Non-trivial property - some elements satisfy and some elements do not satisfy Non- monotonic property- (i)"some property holding element must be a proper subset of "some" property violating element (ii) non-trivial Examples of trivial, non-trivial and non-monotonic properties on recursively enumerable set RICE'S THEOREM: 1) Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable 2) Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable Examples of Rice's theorem Dovetailing method- example: Whether a language L accepted by TM, M has atleast 5 strings?- semi-decidable Check if a language L is infinite?- not a non-monotonic property- can be proved by reduction from a 'not even semi-decidable' language. If PDA is accepting strings of lenth n and 2n, using PL it can be proved that PDA is infinite- where n is pumping lemma constant Oct 6 More examples on Rice's theorem Reducing a problem to Halting problem or non-halting problem Some trivial and non trivial properties of Turing machine description and proof for decidability(cannot use Rice's theorem- it is about TM and not about language accepted by TM) If TM is restricted form writing on tape, what language can it accept?- Regular language Read-Only tape- set of regular languages- Can it accept anymore language- No, there is no extra power on moving left Multi-R/W Tape- No extra power(adds to time complexity) Non- determinism- No extra power How to detect infinite loop in a program? - search for keywords or by checking repeated memory sequence - TM can output "No" for some cases but not for all inputs. TM movement in one direction only- finite movement or configuration, all problems of undecidability is due to reverse movement of R/W head of tape.

4
Like 1
Love 0
Haha 0
Wow 0
Angry 0
Sad 