Suppose Aand Bare sets, f = A → Band g = B → A. If f(g(y)) = y for every y ∈ B, then f is a _______ function and g is a ______ function. Give reasons for your answers.
[3 marks]Given three statements p, q and r. p:a = 1,q:b = 0,r:c = 3. Write tℎe following statements symbolically,using p,q,r,⋁,⋀ ,¬ and → only. 1. Either a = 1 or b ≠ 0. 2. b = 0 , but neither a = 1 nor c = 3.
[4 marks]Discuss3 p. um ping lemma for regular languages. 4.
[7 marks]Define Chomsky Normal Form of grammar. 5.
[3 marks]Define a Moore machine. 6.
[4 marks]Apply the rules and convert the given NFA-λ to FA.
[7 marks]Draw the NFA-λ for r = (0)11* + (101)* 0 and also construct the equivalent NFA and FA for the same.
[7 marks]Given two languages Land Ldefined over Σ = {a,b}∗, Laccepts palindrome strings and Laccepts strings with equal number of 0’s and 1’s. Which one of these2 languages is regular? Give reasons.
[3 marks]Show how, if a pushdown automaton recognizes some language, then it is context free.
[4 marks]If a regular expression is given as (001)* (01 + 10). Apply the rules to construct a regular grammar for this language.
[7 marks]Construct a Finite Automata that accepts all strings containing 010 or 111 as sub- string only.1
[3 marks]Apply pumping lemma to show that the language L = {anbncn | n ≥ 0} is not context free.
[4 marks]Apply the rules and show step by step conversion of the following grammar to CNF. S → ASA | aB A → B | S B → b | ϵ
[7 marks]Define DPDA with clear definition of δ (transition function).
[3 marks]Discuss intersection of CFLs with an example.
[4 marks]Apply the rules and step by step create a Turing Machine to accept L = {anbn}
[7 marks]The language of DPDA is called DCFL. Explain whether this statement is true or false.
[3 marks]Discuss complement of CFLs with an example.
[4 marks]Construct a Turing machine to accept even palindrome over Σ = {a,b}*
[7 marks]Explain the concept of undecidable problems.
[3 marks]Discuss multi-tape Turing machine.
[4 marks]Write a note on Primitive Recursive functions.
[7 marks]Alanguage is decidable if and only if some nondeterministic Turing machine decides it. Explain the statement.
[3 marks]Regular languages and CFLs are both decidable and Turing-recognizable. Explain whether true or false.
[4 marks]Define and explain Bounded Quantification.
[7 marks]