Say whether the statement (p ᴧ (p → q)) → q is tautology or contradiction.
[3 marks]The given relation Ron set A= {1,2,3} determine whether the Relation is reflexive, symmetric or transitive, give reason. R ={(1,1), (1,2), (2,1), (2, 2), (3,2),(3,3)}
[4 marks]Write Principle of Mathematical Induction. And prove for every n ≥ 1,
[7 marks]Define FA and Write recursive definition of NFA
[3 marks]04 Find a regular expression of following subsets of {0, 1}* 1. The language of all strings that begin or end with 00 or 11. 2. The language of all strings ending with 1 and not containing 00.
[ marks]Draw Finite Automata to accept following over input alphabets Σ ={0, 1}
[7 marks]The language accepting strings not ending with ’01’ . (ii)The language accepting strings not containing substring ‘00’
[ marks]07 Let M1 and M2 be the FAs pictured in Figure, recognizing languages L1 and L2 respectively. M1-- M2-- Draw FAs recognizing the following languages. a. L1 U L2 b. L1 - L2
[ marks]Find context-free grammar for the language: L= {aibjck | i=j+k}
[3 marks]Define mealy machine. Design and mealy machine that gives output ‘x’ if input of sequence is abb, otherwise z.
[4 marks]Convert NFA- Λ to FA for following figure.1
[7 marks]Define Ambiguous grammar. for following grammar say whether the grammar is ambiguous or not. give reason S→ABA, A→aA | Λ , B→bB | Λ
[3 marks]Convert the given Moore machine into Mealy machine. Draw state transition diagram of Mealy machine. Present Next State Output State 0 1 →p0 r q0 ɛ p1 r q0 1 q0 p1 s0 0 q1 p1 s0 1 r q1 p1 0 s0 s1 r 0 s1 s1 r 1
[4 marks]Find minimum state FA for following figure.
[7 marks]State pumping lemma for context free language.
[3 marks]04 Construct PDA for S → 0AB A → 1A | 1 B → 0B | 1A | 0 Trace the string 01011 using PDA.
[ marks]Write Kleen’s Theorem part -1.
[7 marks]Define Push Down Automata
[3 marks]Using kleene's Theorem Draw NFA-Λ for a given RE aa(ba)*+b*aba*
[4 marks]Given the context-free grammar G, find a CFG G’ in Chomsky Normal Form. S -> AaA | CA | BaB A -> aaBa | DC B -> bb | aS C -> Ca | bC | D D -> bD | Λ
[7 marks]Explain Universal Turing Machine
[3 marks]Design a PDA to accept L = {xcy | x, y∈ (a,b)* and |x| = |y|}.
[4 marks]Develop a Turing Machine to accept palindromes over {a,b}*
[7 marks]Define grammar and Chomsky hierarchy.
[3 marks]Design a PDA to accept L = {aibjCk| j = i+k}.
[4 marks]Develop a Turing Machine to accept the language L = {X / N (X)=N (X) , a b X ∈ {a,b}*}3
[7 marks]