Define one-to-one, onto and bijection function.
[3 marks]Explain reflexivity, symmetry, and transitivity properties of relations.
[4 marks]State the principle of mathematical induction and prove by mathematical induction that for all positive integers n 1+2+3+……..+n = n (n+1)/2.
[7 marks]What are the closure properties of regular languages?
[3 marks]Explain moore machine and mealy machine.
[4 marks]What are the applications of finite automata? Draw Finite Automata to accept following.
[7 marks]the language accepting strings ending with ’01’ over input alphabets Σ = {0, 1} (ii) the language accepting strings ending with ‘abba’ over input alphabets Σ = {a, b}
[ marks]Define NFA-Ʌ. Explain how to convert NFA-Ʌ into NFA and FA with suitable example.
[7 marks]State pumping lemma for regular languages.
[3 marks]Explain Union Rule and Concatenation Rule for Context Free Grammar.
[4 marks]Write difference between DFA and NDFA. Convert the following NDFA to DFA.
[7 marks]03 Define Context-Sensitive Grammar. What is the language of following context-sensitive grammar? S aTb | ab aT aaTb | ac.
[ marks]Find a regular expression corresponding to each of the following subsets of {0, 1}*
[4 marks]The language of all strings that begin or end with 00 or 11.1 (ii) The language of all strings beginning with 1 and ending with 0.
[ marks]What is CNF? Convert the following CFG into CNF. S → ASA | aB, A → B | S, B → b | ε
[7 marks]What is Turing Machine? Write advantages of TM over FSM.
[3 marks]Define CFG. When a CFG is called an ‘ambiguous CFG’?
[4 marks]Define PDA. Describe the pushdown automata for language {0n1n | n≥ 0}.
[7 marks]Write a short note on Universal Turing Machine.
[3 marks]Describe recursive languages and recursively enumerable languages.
[4 marks]Explain push down automata with example and their application in detail.
[7 marks]Define grammar and chomsky hierarchy.
[3 marks]What are the applications of regular expressions and finite automata?
[4 marks]Draw a transition diagram for a Turing machine for the language of all palindromes over {a, b}.
[7 marks]Compare FA, NFA and NFA-^.
[3 marks]Write a short note on church-turing thesis.
[4 marks]Explain primitive recursive function by suitable example.
[7 marks]