Discuss various types of function with example.
[3 marks]Prove using contra positive proof method: For x ∈ Z, if 7x + 9 is even, then x is odd
[4 marks]Summarize principal of mathematical induction and prove 1 + 4 + 7 + … + (3n – 2) = n(3n – 1)/2 using the same.
[7 marks]Give formal definition of NFA
[3 marks]• Construct DFA over = {a, b} which accepts all the strings of length at least • Design FA for |w| mod 3 = 0
[2 marks]07 Let Mand Mbe DFA representing languages Land Lrespectively. Construct combined DFA which accepts the language L L .12
[ marks]Minimize following DFA using state minimization method.
[7 marks]State the differences between DFA and NFA
[3 marks]Explain -Closure. Find -Closure of following -NFA1
[4 marks]Convert following NFA to DFA
[7 marks]Write regular expression for following languages over = {0, 1} • Strings having odd number of 1 • Strings having 1 as second last symbol
[3 marks]Compare and contrast Mealy and Moore Machine
[4 marks]Write CFG for following languages over = {a, b}: • Even length Palindrome • String starting and ending in different symbols
[7 marks]Illustrate left and right most derivation for the string “bbaaab” using following grammar: S → aB | bA A → a | aS | bAA B → b | bS | aBB
[3 marks]Illustrate unambiguous grammar with suitable example
[4 marks]Convert following CFG to CNF: S → ABA A → aA | B → bB |
[7 marks]Construct PDA for following grammar: S → AB, A → CD, B → b, C → a, D → a
[3 marks]Design PDA for L = {anbncmdm | n >=0, m > 1 }
[4 marks]Explain Pumping lemma for CFG. Using pumping lemma, show that L = {anbncn | n >=0} is not CFL
[7 marks]Write brief note on Church Turing Thesis
[3 marks]Illustrate the design of Turing machine to find 2’s complement of binary number
[4 marks]Construct Turing machine for language: L = {anbncn | n >= 1}
[7 marks]Explain partial, total and constant function with example.
[3 marks]Summarize working of primitive recursion
[4 marks]Discuss Primitive predicate and Bounded Mineralization
[7 marks]