1 
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 contextsensitive and recursive language space complexity is linear in LBA, find an example for language accepted by TM but not LBA 


2 
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 nonterminal on left of each production
Right linear grammar only one nonterminal 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.



3 
Sep 29 
Half(L) is regular  how to construct DFA for Half(L)
Squareroot(L) is regular
Square(L) is not regular 


4 
Sep 30Oct 2 
Solve GO pdf questions on regular language,regular expressions and context free languages 


5 
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 viceversa.
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. 


6 
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
Semidecidable, Language is Recursively Enumerable
Halting problem
Case 3:
It cannot output "Yes" for all "yes" cases
Not even semidecidable, 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 semidecidable and undecidable.
Complement of Halting problem is not even semidecidable 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 


7 
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
Nontrivial 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) nontrivial
Examples of trivial, nontrivial and nonmonotonic properties on recursively enumerable set
RICE'S THEOREM:
1) Any nontrivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable
2) Any nonmonotonic 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? semidecidable
Check if a language L is infinite? not a nonmonotonic property can be proved by reduction from a 'not even semidecidable' 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 


8 
Oct 6 
More examples on Rice's theorem
Reducing a problem to Halting problem or nonhalting 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
ReadOnly tape set of regular languages Can it accept anymore language No, there is no extra power on moving left
MultiR/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. 

