What is a proposition? Which logical connectives do we use to generate compound proposition?
[3 marks]Out of these two statements which one is true and which is false. Justify your answer. 1. ∀x(∃y((x− y)2 < 4 )) 2. ∃y(∀x((x− y)2 < 4 ))
[4 marks]Develop an FA corresponding to following regular expression r = (11+110)∗0 Explain the properties of Distinguishability of Strings and Equivalence classes, show minimum numbers of states necessary for this FA.
[7 marks]Write the strong principle of mathematical induction and show that P(n) is true for everyn ≥ 2, where P(n) is the statement: n is either a prime or a product of two or more primes.
[3 marks]Define a CFG for language having strings with equal number of 0’s and 1’s. L = { x ∈ {0,1}∗ | n (x) = n (x)}01
[4 marks]Lis a language over {0, 1}* that accepts strings ending in 11. Lis a12 language over {0, 1}* that accepts strings containing 101 as sub-string. Write the regular expressions, draw FA for Land Land derive FA for L U L .
[7 marks]Apply the subset construction technique to convert the given NFA to FA.1
[7 marks]What is an Ambiguous CFG? Explain with reference to dangling else problem.
[3 marks]Explain Moore machine and Mealy machine. Give example of two equivalent machines of each type performing similar function.
[4 marks]Derive a CFG equivalent to following regular expression (011+1)∗(01)∗
[7 marks]What are Nullable variable in a CFG? How can we remove them from a production?
[3 marks]Draw NFA-Λ for ((0+1)*10 + (00)*(11)*)*
[4 marks]What are the steps to convert a CFG to Chomsky Normal Form?
[7 marks]Define a Turing Machine.
[3 marks]What language will be generated by this CFG: S → aT | bT | Λ T → aS | bS
[4 marks]Develop a DPDA that accepts following language: L = {x ∈ {a,b}∗ |n (x) > n (x)} a b
[7 marks]What is the difference between accepting a Language and Recognizing a Language?
[3 marks]Give transition tables for PDA recognizing the language of all non- palindromes over {a,b}*
[4 marks]Write the pumping lemma for Context-Free Languages and prove that L = { aibici|i ≥ 1} is not a CFL.
[7 marks]Define Primitive Recursive Functions.
[3 marks]Draw a Turing Machine to accept a regular language {a, b}*{aba}
[4 marks]Develop a Turing Machine to accept even length palindromes over {a,b}*
[7 marks]Define Bounded Minimalization of a predicate P.
[3 marks]What important points do we derive from Church-Turing thesis?
[4 marks]Develop a Turing Machine that creates a copy of its input string to the right of the input but with a blank space separating the copy from the original.
[7 marks]