Define - bijection. Let A = {1, 2, 3} and B = {a, b}. Check whether the function f = {(1, a), (2, b), (3, a)} is bijection or not? Justify your answer with reasons.
[3 marks]Define - Equivalence relation. Let A = {0, 1, 2, 3} and a relation Ron A is defined as R = {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (2, 2), (3, 0), (3, 3)}. Is R Reflexive? Symmetric? Transitive? Equivalence? Justify your answer in each case.
[4 marks]Using the principle of mathematical induction, for all n > 0, prove that, {1 - (½)} {1 - (⅓)} {1 - (¼)} ….. {1 - (1/(n+1))} = 1/(n+1)
[7 marks]Convert the following Mealy machine into its equivalent Moore Machine:
[3 marks]Find context-free grammars that generate the following languages:
[4 marks]L = {ai bj ck | i = j + k}1 (ii) L = {ai bj ck | j = i or j = k}2
[ marks]Using the subset construction method, convert the following NFA into its equivalent DFA accepting the same language.
[7 marks]Using the subset construction method, convert the following NFA into its equivalent DFA accepting the same language.1
[7 marks]Find a regular expression corresponding to each of the following subsets of {a, b}*:
[3 marks]The set of all the strings with length 5 exactly and next to last symbol is ‘b’ (ii) The set of all strings that ends with sub-string ‘abb’ (iii) The set of all strings having ‘a’ as the first symbol and ‘b’ as the last symbol
[ marks]Let Mand Mbe the FAs accepting languages Land Lrespectively. Draw FAs accepting the L U Llanguage.21
[4 marks]Find a minimum-state FA for the following FA that recognizes the same language.
[7 marks]Discuss μ-recursive functions.
[3 marks]Describe recursively enumerable languages and recursive languages.
[4 marks]What is decidability? How to prove that the given language is undecidable? List some undecidable problems.
[7 marks]Discuss pumping lemma for context-free languages.
[3 marks]Discuss two situations of Turing machine crashing with example.
[4 marks]Build a TM that accepts the language PALINDROME over {a, b}*. Also trace out the same on the input string abba.
[7 marks]Decide whether the language L = {anbmambn | m, n ≥ 0} is a CFL or not and prove your answer.
[3 marks]Define - Pushdown Automaton and acceptance by a PDA
[4 marks]Draw Turing machine that accepts the language {anbncn | n ≥ 0} over {a, b, c}*. Also trace out the same on the input string aabbcc.
[7 marks]Define bounded minimalization of a predicate P.
[3 marks]Discuss primitive recursive functions with the help of a suitable example.
[4 marks]Design a PDA to accept strings with more a’s than b’s. Also trace out the same on input string abbabaa.2
[7 marks]Define ambiguous grammar. Check whether the CFG with productions, S → a | Sa | bSS | SSb | SbS is ambiguous or not.
[3 marks]For each of the following, describe the language generated by given CFG:
[4 marks]S → SaS | b (ii) S → aT | bT | Λ T → aS | bS
[ marks]Define Chomsky Normal Form (CNF). Convert the following CFG into its equivalent CNF. S → aY | Ybb | Y X → Λ | a Y → aXY | bb | XXa
[7 marks]