Show that (p → ¬ p) V (¬ p → p) is a tautology.
[3 marks]Prove that for any; n ≥ 4,n! > 2n.
[4 marks]Explain the concept of “Language” and discuss how FA, which accepts or rejects a language, is constructed using a regular expression.
[7 marks]Define: Context Free Language.
[3 marks]Write only the algorithmic steps to minimize a given finite automata.
[4 marks]Apply the rules to convert NFA to FA and create a minimum state FA for the given NFA here.
[7 marks]Apply pumping lemma for regular languages and prove that the language of palindromes is not regular.
[7 marks]Apply the rules and draw NFA – λ for ((0)* + (1)*) (00)*(1)
[3 marks]Apply the rules to construct NPDA for accepting a palindrome.
[4 marks]Apply the rules and convert regular expression to regular grammar for the given regular expression. (011 + 1)* (01)*1
[7 marks]Apply the rules to find λ - closure of set of states for the given NFA- λ and find λ(A), λ(B), λ(C) and λ(D). q 𝜹(q,𝝀) 𝜹(q,0) 𝜹(q,1) A {B} {A} ∅ B {D} {C} ∅ C ∅ ∅ {B} D ∅ {D} ∅
[3 marks]Explain Context Free Languages.
[4 marks]Apply the method to check if the given grammar is unambiguous or not: expr → expr + expr | expr * expr | (expr) | d
[7 marks]Why is the “Pushdown” automata called “push-down” automata?
[3 marks]Given a regular expression, you can always create a PDA for it. Explain the statement.
[4 marks]Apply the rules and draw the TM for the language of odd palindromes.
[7 marks]The FA is more powerful than DPDA. Explain if True or False?
[3 marks]Discuss the pumping lemma for CFL.
[4 marks]Apply the rules and draw the TM to accept the language L = {ab}*{aba} over Σ = {a,b}*
[7 marks]Define decidability of a language.
[3 marks]Discuss Chomsky hierarchy.
[4 marks]Discuss Primitive Recursive Functions.
[7 marks]What is a post correspondence problem?
[3 marks]Discuss Church-Turing thesis.
[4 marks]Show how all computable functions are 𝜇 -recursive.
[7 marks]