Let f be a function from the set A = {1,2,3,4} to B = {p, q,r,s} such that, f = {(1,p)(2,p)(3,q)(4,s)}. Is f−1 a function?
[ marks]Lis defined recursively as follows: 1. 𝜖 ∈ L 2. ∀x ∈ L, both 0x and 0x1 are inL. Prove that: For every n >= 0, every x belongs to Lobtained by n applications of rule 2 is an element of L.
[4 marks]Discuss “Distinguishability” of one string from another and explain how it affects the number of states in an FA. Considering the example of L = {a,b}∗{aba}, how do the distinguishable strings in Lrelate to the number of states in its FA?
[7 marks]Define: Grammar.
[3 marks]What are similarities and differences between Moore machines and Mealy04 machines?
[ marks]Given two languages Land L , defined as:12 L = {x | all x start witℎ aba }1 L = {x | all x ends in bb}207 Write the regular expression for both the languages and construct FAs Mand M12 such that Maccepts Land Maccepts L . Derive L ∩ L .
[ marks]Draw the given NFA in Table-1 and convert it to FA and identify the language.07 q0 is the initial state and q1 is the accepting state.
[ marks]Draw NFA lambda for the given regular expression: (0)* (00 + 11)* (001) (01 + 10)
[ marks]Explain the Pumping Lemma for Context Free Languages.
[4 marks]Convert the following grammar to CNF. S → ABA07 A → aA | ϵ B → bB | ϵ
[ marks]Find the ꓥ-closure of a set of states for each state of the given NFA lambda in Figure-1.
[ marks]What are non-CFLs? Give at-least two examples of non-CFLs.
[4 marks]Show Bottom Up Parsing of the string “id + id * id” using the following grammar. E → E + T | T T → T * F | F1 F → (E) | id
[7 marks]Define PDA. State whether a PDA can accept a CFL or not.
[ marks]Discuss the closure properties of CFLs.
[4 marks]For the given Turing Machine in Table-2, trace the transition for the strings and 10101 and identify the language recognized by this TM. TM is defined as TM07 = (Q, Σ, Γ, q , δ ) where {q ,q ,q ,q ,q ,q ,q } ∈ Q, Σ = {0,1}, {0,1,X,Y,B} ∈ Γ, q ∈ Q, B ∈ Γ , B ∉ Σ, {q } is the accepting state.06
[ marks]Compare NPDA with DPDA.
[3 marks]Show that if there are strings x and y in the language Lso that x is a prefix of y04 and x ≠ y, then no DPDA can accept Lby empty stack.
[ marks]Draw a TM for the Language of strings with balanced parenthesis “(” and “)” only.
[7 marks]When can we say that the language is decidable or undecidable?
[3 marks]Draw only the transition table of Turing Machine to accept the language L = {0n1n: wℎere n ≥ 1}
[4 marks]Define: Bounded Minimalization and show that, if Pis a primitive recursive (n+ 1) place predicate, its bounded minimalization mP is a primitive recursive function.
[7 marks]When can the language be called a recursive language or a recursively enumerable language?
[3 marks]Show that a Turing Machine to recognize the language L = L(0∗1) can accept the string without moving the head in Ldirection.
[4 marks]Define: 𝜇-Recursive functions and show how all computable functions are 𝜇 - recursive. Table-1 Table-2 𝛿(q,0) 𝛿(q,1) State 0 1 X Y B q {q ,q } {q } q (q1,X,R) (q2,Y,R) (q6,X,R) (q6,Y,R) (q6,B,R)0 q {ø} {q ,q }101 q (q1,0,R) (q1,1,R) (q3,X,L) (q3,Y,L) (q3,B,L)1 q (q2,0,R) (q2,1,R) (q4,X,L) (q4,Y,L) (q4,B,L)2 q (q5,X,L) — (q6,X,R) (q6,Y,R) —3 q — (q5,Y,L) (q6,X,R) (q6,Y,R) —4 q (q5,0,L) (q5,1,L) (q0,X,R) (q0,Y,R) —5 Figure-1 =======xx===========xxxxxxxxxxx=======xx======xxxxxxxxxx=============xx=====2
[7 marks]