Explain on to, one to one, and Bijection Function with suitable example.
[3 marks]Explain reflexivity, symmetry, and transitivity properties of relations.
[4 marks]What is PMI? Prove 7+ 13+19+…..+(6n+1)= n(3n+4) using PMI.
[7 marks]Find regular expression for following I. Language of all strings containing exactly two 0’s. II. Language of all strings that begins or ends with 00 or 11.
[3 marks]Compare FA, NFA and NFA-^.
[4 marks]Draw Finite Automata (FA) for following languages: L1 = {x / 00 is not a substring of x } L2 = {x / x ends with 01 } Find FA accepting languages (i) L1 ∩ L2 and (ii) L2 – L1
[7 marks]Define NFA – Λ. Explain how to convert NFA – Λ into NFA and FA with suitable example.
[7 marks]Draw FA for each of the following RE. (a+b)*baaa
[3 marks]Define pumping lemma and its application.
[4 marks]For the following CFG, Find Chomsky normal form S→AACD A→aAb|ᴧ C→ aC|a D→aDa|bDb|ᴧ
[7 marks]Consider the grammar: S→aAS | a1 A→ SbA | SS | ba Derive left most and right most derivation of string aabbaa using given grammar.
[3 marks]Define CFG. Create CFG for (011+1)*(01)*
[4 marks]Design a TM for accepting Palindromes for odd and even length.
[7 marks]What is Turing Machine? Write advantages of TM over FSM.
[3 marks]Explain Ambiguous Grammar and remove ambiguity with suitable example.
[4 marks]Design PDA for L={x∈xr/x∈{a,b}*}. The string in Lare odd length palindromes over {a,b}.
[7 marks]Define Constant functions, Successor functions and Projection function.
[3 marks]Write a note on DPDA and NPDA
[4 marks]Design a deterministic PDA Accepting “Balance string of brackets”.
[7 marks]Enlist limitations of Turing machines.
[3 marks]Explain moore machine and mealy machine.
[4 marks]Discuss Universal Turing Machine with suitable example.
[7 marks]Write Short note on Church-Turing Thesis.
[3 marks]Define P, NP, NP-Hard and NP-Complete problem?
[4 marks]Explain Halting Problem with suitable example.
[7 marks]