BEU TOC 5th Sem Previous Year Objective Questions with Solutions

Paper 1: B.Tech 5th Semester Exam, 2021 (Code: 105503)

1. (a) Which of the following statements is/are False?

• A. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
• B. Turing recognizable languages are closed under union and complementation.
• C. Turing decidable languages are closed under intersection and complementation.
• D. Turing recognizable languages are closed under union and intersection.
  • (i) A and D only
  • (ii) A and C only
  • (iii) B only
  • (iv) C only
• Answer: (iii) B only
• Explanation:
  • A is True: Non-deterministic Turing Machines (NTMs) and Deterministic Turing Machines (DTMs) are equivalent in power. Any language recognized by an NTM can be recognized by a DTM.
  • B is False: Turing recognizable (Recursively Enumerable) languages are closed under union and intersection, but not under complementation. If a language and its complement are both Turing recognizable, then the language is decidable.
  • C is True: Turing decidable (Recursive) languages are closed under all boolean operations: union, intersection, and complementation.
  • D is True: As stated above, Turing recognizable languages are closed under union and intersection.
    Therefore, only statement B is false.

1. (b) Enumerator is a Turing machine with…

• (i) an output printer
• (ii) 5 input tapes
• (iii) a stack
• (iv) None of the above
• Answer: (i) an output printer
• Explanation: An enumerator is a variation of a Turing Machine that is designed to generate (enumerate) all the strings of a language. It typically has a work tape and a special output tape, often called a “printer,” onto which it writes the strings of the language, separated by a special symbol. It starts with a blank tape and keeps printing the strings of the language forever if the language is infinite.

1. (c) The language {a^m b^n c^(m+n) | m, n ≥ 1} is…

• (i) regular
• (ii) context-free but not regular
• (iii) context-sensitive but not context-free
• (iv) type-0 but not context-sensitive
• Answer: (ii) context-free but not regular
• Explanation:
  • Not Regular: A finite automaton cannot remember the count of m ‘a’s and n ‘b’s to match them with m+n ‘c’s. This requires unbounded memory, which violates the Pumping Lemma for regular languages.
  • Context-Free: A pushdown automaton (PDA) can recognize this language. It can push a symbol for each ‘a’, then push another symbol for each ‘b’, and then pop one symbol from the stack for each ‘c’. If the stack is empty after reading all ‘c’s, the string is accepted.

1. (d) The maximum number of states of a DFA converted from an NFA with n states is…

• (i) n
• (ii) n²
• (iii) 2^n
• (iv) None of the above
• Answer: (iii) 2^n
• Explanation: The standard algorithm for converting a Non-deterministic Finite Automaton (NFA) to a Deterministic Finite Automaton (DFA) is the subset construction. Each state in the resulting DFA corresponds to a subset of states from the original NFA. A set with n elements has 2^n possible subsets. Therefore, the maximum number of states in the equivalent DFA is 2^n.

1. (e) If L1 and L2 are context-free languages, L1-L2 is __ context-free.

• (i) always
• (ii) sometimes
• (iii) never
• (iv) None of the above
• Answer: (ii) sometimes
• Explanation: The class of context-free languages is not closed under set difference (L1 – L2) or intersection. This means you cannot guarantee that the result will be context-free. However, it’s not “never” context-free either. For a simple example, if L2 is the empty language, L1 – L2 = L1, which is context-free. Therefore, the result is “sometimes” context-free.

1. (f) Which of the following does not have left recursions?

• (i) Chomsky normal form
• (ii) Greibach normal form
• (iii) Backus-Naur form
• (iv) All of a the above
• Answer: (ii) Greibach normal form
• Explanation: A grammar is in Greibach Normal Form (GNF) if all its production rules are of the form A → aα, where a is a terminal symbol and α is a (possibly empty) string of non-terminals. Since every production must start with a terminal, left recursion (e.g., A → Aβ) is impossible by definition.

1. (g) Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true?

• (i) m ≤ 2^n
• (ii) n ≤ m
• (iii) M has one accept state
• (iv) m = 2^n
• Answer: (i) m ≤ 2^n
• Explanation: From the subset construction, the DFA equivalent to an n-state NFA has at most 2^n states. The minimized DFA (M) will have a number of states (m) less than or equal to this upper bound. m is not necessarily equal to 2^n, and n can be greater than m.

1. (h) __ is the acyclic graphical representation of a grammar.

• (i) Binary tree
• (ii) Octtree
• (iii) Parse tree
• (iv) None of the above
• Answer: (iii) Parse tree
• Explanation: A parse tree (or derivation tree) is a rooted, ordered tree that represents the syntactic structure of a string according to a grammar. It is inherently acyclic and shows how the start symbol of a grammar can derive a particular string.

1. (i) A minimum state deterministic FA accepting the language L = {w|w∈ {0, 1}*} where number of 0’s and 1’s in w are divisible by 3 and 5 respectively, has…

• (i) 15 states
• (ii) 11 states
• (iii) 10 states
• (iv) 9 states
• Answer: (i) 15 states
• Explanation: To solve this, we need a DFA that tracks two independent conditions: (count of 0s mod 3) and (count of 1s mod 5). We can use a product construction. A DFA for (count of 0s mod 3) needs 3 states. A DFA for (count of 1s mod 5) needs 5 states. The resulting DFA needs a state for each pair of states from the original machines, so it will have 3 × 5 = 15 states.

1. (j) The construction time for DFA from an equivalent NFA (m number of node) is…

• (i) O(m²)
• (ii) O(2^m)
• (iii) O(m)
• (iv) O(log m)
• Answer: (ii) O(2^m)
• Explanation: The subset construction algorithm, in the worst case, must generate and process all 2^m subsets of the NFA’s states. For each of these new DFA states, it must compute transitions for every symbol in the alphabet. This leads to a worst-case time complexity that is exponential in the number of NFA states (m).

Paper 2: B.Tech 5th Semester Exam, 2022 (Code: 105503)

1. (a) The language { a^m b^n c^(m+n) / m, n ≥ 1}

• (i) regular
• (ii) context-free but not regular
• (iii) Context-sensitive but not context free
• (iv) type-0 but not context sensitive
• Answer: (ii) context-free but not regular
• Explanation: This is identical to question 1(c) from the 2021 paper. A PDA can handle the counting, but an FA cannot.

1. (b) Which of the following pairs have DIFFERENT expressive powers?

• (i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)
• (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
• (iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine
• (iv) Single-tape Turing machine and multi-tape Turing machine
• Answer: (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
• Explanation:
  • (i) DFAs and NFAs are equivalent in power; they both accept the class of regular languages.
  • (ii) NDPDAs are strictly more powerful than DPDAs. NDPDAs accept all context-free languages, while DPDAs only accept the subset of deterministic context-free languages.
  • (iii) & (iv) All variants of Turing machines (deterministic, non-deterministic, single-tape, multi-tape) are equivalent in expressive power.

1. (c) The logic of pumping lemma is a good example of…

• (i) pigeon-hole principle
• (ii) divide-and-conquer technique
• (iii) recursion
• (iv) iteration
• Answer: (i) pigeon-hole principle
• Explanation: The Pumping Lemma works because a sufficiently long string must cause the automaton to repeat a state (pigeons = positions in the string, holes = states). This repetition allows a subsection of the string to be “pumped” (repeated or removed). This core idea is a direct application of the Pigeonhole Principle.

1. (d) If L1 and L2 are context free languages, L1 – L2 is __ context-free.

• (i) always
• (ii) sometimes
• (iii) never
• (iv) None of these
• Answer: (ii) sometimes
• Explanation: This is identical to question 1(e) from the 2021 paper. CFLs are not closed under set difference.

1. (e) __ is the acylic graphical representation of a grammer

• (i) Binary tree
• (ii) Octtree
• (iii) Parse tree
• (iv) None of the above
• Answer: (iii) Parse tree
• Explanation: This is identical to question 1(h) from the 2021 paper.

1. (f) Which of the following pairs of regular expressions are equivalent?

• (i) x* and xx
• (ii) 1(01)* and (10)*1
• (iii) x(xx)* and (xx)*x
• (iv) All of the above
• Answer: (iv) All of the above
• Explanation:
  • (i) x* (zero or more x’s) concatenated with x* is still just zero or more x’s. Equivalent.
  • (ii) Both expressions describe strings of alternating 1s and 0s that start and end with a 1. Equivalent.
  • (iii) Both expressions describe strings containing an odd number of x’s. Equivalent.

1. (g) The maximum number of states of a DFA converted from an NFA with n states is…

• (i) n
• (ii) n^2
• (iii) 2
• (iv) None of these
• Answer: (iv) None of these
• Explanation: The correct answer is 2^n. Since this is not listed as an option, “None of these” is the correct choice. (It is highly likely that option (iii) was a typo and should have been 2^n).

1. (h) Definition of a language L with alphabet {a} is given as L= {a^(nk) / k > 0, and n is a positive integer constant}. What is the minimum number of states needed in a DFA to recognize L?

• (i) k + 1
• (ii) n + 1
• (iii) 2n + 1
• (iv) 2k + 1
• Answer: (ii) n + 1
• Explanation: The language consists of strings of ‘a’s whose length is a multiple of n. A DFA to recognize this language needs to count the number of ‘a’s modulo n. This requires n states (for remainders 0, 1, …, n-1) to cycle through, plus one non-accepting state if the string is empty and k must be > 0. A standard construction requires a start state, n-1 intermediate states, and one accepting state (which is reached after n, 2n, 3n… ‘a’s). This totals n states. However, you also need a dead/trap state for invalid input if the alphabet was larger. With only ‘a’, a cycle of n states works. Let’s re-evaluate. The set of lengths is {n, 2n, 3n, …}. A DFA can have states q0, q1, ..., q(n-1). q0 is the start state. Transitions are δ(qi, a) = q(i+1) mod n. The only accepting state is q0. This requires n states. But wait, k>0, so the empty string is not accepted. A common construction uses n+1 states: a start state, n-1 intermediate states, an accepting state, and a non-accepting start state if n itself is the cycle length. The minimal DFA for {a^(nk) | k>=1} has n states, where one state is final. The minimal DFA for {a^n} has n+2 states. For {a^(nk) | k>=0}, it is n states. The question as stated, {a^(nk) | k > 0}, which is the same as k>=1, is recognized by a DFA with n states. Hmm, let’s check standard interpretations. Often, a sink state is included. So n states for the cycle + 1 sink state. Let’s reconsider n+1. The language (a^n)+ needs n states for the cycle plus a starting non-final state that goes to state 1 on ‘a’. So n+1 states. Let’s take n=2, L={aa, aaaa, …}. We need q0->q1 on a. q1->q2 on a. q2 is final. q2->q1 on a. That’s 3 states (n+1). Let’s take n=3, L={aaa, …}. q0->q1->q2->q3. q3 is final. q3->q1. That’s 4 states. So n+1 seems correct.

1. (i) A __ is context free grammar with atmost one non-terminal in the right handside of the production.

• (i) linear grammar
• (ii) linear bounded grammar
• (iii) regular grammar
• (iv) None of the above
• Answer: (i) linear grammar
• Explanation: This is the definition of a linear grammar. A production is linear if its right-hand side contains at most one non-terminal. A regular grammar is a specific type of linear grammar (either right-linear or left-linear).

1. (j) Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true?

• (i) m ≤ 2^n
• (ii) n ≤ m
• (iii) M has one accept state
• (iv) m = 2^n
• Answer: (i) m ≤ 2^n
• Explanation: This is identical to question 1(g) from the 2021 paper.

Paper 3: B.Tech 5th Semester Exam, 2023 (Code: 105503)

1. (a) Let S be an infinite countable set. Then its power set will be…

• (i) countable
• (ii) not countable
• (iii) can’t be determined
• (iv) None of the above
• Answer: (ii) not countable
• Explanation: This is a result of Cantor’s theorem, which states that the cardinality of the power set of a set A is strictly greater than the cardinality of A. If S is countably infinite (like the natural numbers), its power set P(S) is uncountably infinite (it has the cardinality of the continuum).

1. (b) Assuming P != NP, which of the following is true?

• (i) NP-complete = NP
• (ii) NP-complete ∩ P = ∅
• (iii) NP-hard = NP
• (iv) P = NP-complete
• Answer: (ii) NP-complete ∩ P = ∅
• Explanation: The class NP-complete consists of the “hardest” problems in NP. If any NP-complete problem could be solved in polynomial time (i.e., was in P), then all problems in NP could be. The assumption P != NP means that no NP-complete problem is in P. Therefore, their intersection is the empty set.

1. (c) Which of the following pairs of regular expressions is not equivalent?

• (i) 1(01)* and (10)*1
• (ii) (ab)* and ab
• (iii) x(xx)* and (xx)*x
• (iv) x+ and x*x+
• Answer: (ii) (ab)* and ab
• Explanation:
  • (i) Equivalent (strings of alternating 1s and 0s, starting/ending with 1).
  • (ii) Not equivalent. (ab)* generates {ε, ab, abab, …}. a*b* generates {ε, a, b, aa, ab, bb, …}. The string “a” is in a*b* but not in (ab)*.
  • (iii) Equivalent (strings with an odd number of x’s).
  • (iv) Equivalent. x+ is one or more x’s. x*x+ is zero or more x’s followed by one or more x’s, which is also just one or more x’s.

1. (d) The logic of Pumping Lemma is a good example of…

• (i) The pigeon-hole principle
• (ii) the divide and conquer technique
• (iii) recursion
• (iv) iteration
• Answer: (i) The pigeon-hole principle
• Explanation: This is identical to question 1(c) from the 2022 paper.

1. (e) A PDM behaves like a TM when the number of auxiliary memory it has is…

• (i) 0
• (ii) 1 or more
• (iii) 2 or more
• (iv) None of the above
• Answer: (iii) 2 or more
• Explanation: A standard pushdown machine (PDM/PDA) has one stack. A Turing Machine (TM) is equivalent in power to a PDA with two stacks. One stack is not enough.

1. (f) The recognizing capability of DPDA and NPDA is…

• (i) different
• (ii) same
• (iii) can’t be decided
• (iv) None of the above
• Answer: (i) different
• Explanation: This is identical to question 1(b) from the 2022 paper. NDPDAs are more powerful than DPDAs.

1. (g) If L is a recursive language, then will its complement be also recursive? It is a…

• (i) decidable problem
• (ii) un-decidable problem
• (iii) can’t be said
• (iv) None of the above
• Answer: (i) decidable problem
• Explanation: The class of recursive (decidable) languages is closed under complementation. This means if L is recursive, its complement L’ is also recursive. A language being recursive means the problem of determining membership in it is decidable.

1. (h) If a language and its complement both are recursively enumerable then the language is…

• (i) regular
• (ii) context-free
• (iii) context-sensitive
• (iv) recursive
• Answer: (iv) recursive
• Explanation: This is a fundamental result known as Post’s Theorem. A language is recursive (decidable) if and only if both it and its complement are recursively enumerable (Turing recognizable). (The handwritten answer on the paper is correct).

1. (i) CFG is not closed under…

• (i) union
• (ii) kleene star
• (iii) complementation
• (iv) product (concatenation)
• Answer: (iii) complementation
• Explanation: The class of Context-Free Languages (CFLs) is closed under union, concatenation (product), and Kleene star. It is not closed under intersection or complementation.

1. (j) The intersection of a context-free language and a regular language is…

• (i) need not be regular
• (ii) need not be context-free
• (iii) is always context-free
• (iv) None of the above
• Answer: (iii) is always context-free
• Explanation: This is a standard closure property. The class of context-free languages is closed under intersection with the class of regular languages. The proof involves a product construction of a PDA and a DFA.

Paper 4: B.Tech 6th Semester Exam, 2019 (Code: 051611)

1. (a) The word ‘formal’ in formal languages means…

• (i) they are unnecessary, in reality
• (ii) the symbols used have well-defined meaning
• (iii) only the form of the string of symbols is significant
• (iv) None of the above
• Answer: (iii) only the form of the string of symbols is significant
• Explanation: In the context of formal language theory, “formal” refers to the fact that we are concerned only with the syntax (the structure or form) of the strings, not their semantics (meaning). The languages are defined by strict rules of formation.

1. (b) Which of the following statements is true?

• (i) If a language is context-free, it can always be accepted by a deterministic push-down automaton.
• (ii) The union of two context-free languages is context-free.
• (iii) The intersection of two context-free languages is context-free.
• (iv) The complement of a context-free language is context-free.
• Answer: (ii) The union of two context-free languages is context-free.
• Explanation:
  • (i) is False. Only deterministic context-free languages can be accepted by a DPDA. Non-deterministic CFLs exist.
  • (ii) is True. This is a standard closure property of CFLs.
  • (iii) is False. CFLs are not closed under intersection.
  • (iv) is False. CFLs are not closed under complementation.

1. (c) Which of the following pairs of regular expressions are equivalent?

• (i) x* and xx
• (ii) 1(01)* and (10)*1
• (iii) x(xx)* and (xx)*x
• (iv) All of the above
• Answer: (iv) All of the above
• Explanation: This is identical to question 1(f) from the 2022 paper. All pairs are equivalent.

1. (d) Which of the following pairs have DIFFERENT expressive powers?

• (i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA)
• (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
• (iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine
• (iv) Single-tape Turing machine and multi-tape Turing machine
• Answer: (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA)
• Explanation: This is identical to question 1(b) from the 2022 paper. Only the PDA pair has different power.

1. (e) Definition of a language L with alphabet {a} is given as L = {a^(nk) | k > 0, and n is a positive integer constant}. What is the minimum number of states needed in a DFA to recognize L?

• (i) k+1
• (ii) n+1
• (iii) 2n+1
• (iv) 2k+1
• Answer: (ii) n+1
• Explanation: This is identical to question 1(h) from the 2022 paper. To recognize lengths that are positive multiples of n, a minimal DFA requires n+1 states.

1. (f) Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP complete (NPC)?

• (A) P and NP are separate circles, NPC is inside NP.
• (B) P and NP are overlapping circles, NPC is in the NP-only part.
• (C) P and NP are the same circle, NPC is inside it.
• (D) P is a subset of NP which is a subset of NPC.
• Answer: (iii) C (referring to the image labels)
• Explanation: The clique problem is NP-complete. If an NP-complete problem is found to have a polynomial-time algorithm, it means that this problem is in P. A fundamental property of NP-completeness is that if any NP-complete problem is in P, then all problems in NP are also in P. Therefore, P = NP. Diagram C correctly shows P and NP as the same set, with NPC being a subset of this unified class.

1. (g) Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

• (i) L2 – L1 is recursively enumerable.
• (ii) L1 – L3 is recursively enumerable.
• (iii) L2 ∩ L1 is recursively enumerable.
• (iv) L2 ∪ L1 is recursively enumerable.
• Answer: (ii) L1 – L3 is recursively enumerable.
• Explanation:
  • (i) True. L2 – L1 = L2 ∩ L1′. Since L1 is recursive, its complement L1′ is also recursive. The intersection of a recursively enumerable (RE) language (L2) and a recursive language (L1′) is RE.
  • (ii) Not necessarily true. L1 – L3 = L1 ∩ L3′. L3 is RE but not recursive, so its complement L3′ is not RE. The intersection of a recursive language (L1) with a non-RE language (L3′) is not guaranteed to be RE.
  • (iii) True. The intersection of an RE language (L2) and a recursive language (L1) is RE.
  • (iv) True. The union of an RE language (L2) and a recursive language (L1) is RE.

1. (h) A PDM behaves like an FSM when the number of auxiliary memory it has, is

• (i) 0
• (ii) 1
• (iii) 2
• (iv) None of the above
• Answer: (i) 0
• Explanation: A Finite State Machine (FSM), or Finite Automaton, is a computational model with a finite number of states and no auxiliary memory. A Pushdown Machine (PDM), or Pushdown Automaton, is an FSM augmented with a single stack (one unit of auxiliary memory). If you remove the stack from the PDM, you are left with an FSM. Therefore, a PDM with zero auxiliary memory behaves like an FSM.

Paper 5: B.Tech 5th Semester Exam, 2020 (Code: 105503)

1. (a) Definition of a language L with alphabet {a} is given as L = {a^(nk) | k > 0, and n is a positive integer constant}. What is the minimum number of states needed in a DFA to recognize L?

• (i) k+1
• (ii) n+1
• (iii) 2n+1
• (iv) 2k+1
• Answer: (ii) n+1
• Explanation: This is identical to question 1(h) from the 2022 paper and 1(e) from the 2019 paper.

1. (b) Which of the following versions of Unix came up with YACC first?

• (i) V3
• (ii) V5
• (iii) CB UNIX
• (iv) UNIX-RT
• Answer: (i) V3
• Explanation: YACC (Yet Another Compiler-Compiler) was created by Stephen C. Johnson at AT&T for the Unix operating system. It first appeared in Version 3 Unix (V3).

1. (c) A pushdown automata can be represented as PDA = ε-NFA + [stack].

• (i) True
• (ii) False
• Answer: (i) True
• Explanation: This is a conceptual representation. A pushdown automaton can be thought of as a non-deterministic finite automaton that has been augmented with a stack. The ε-NFA part refers to the finite control and its ability to make non-deterministic and epsilon transitions, and the [stack] is the added memory component.

1. (d) A language accepted by deterministic pushdown automata is closed under which of the following?

• (i) Complement
• (ii) Union
• (iii) Both (i) and (ii)
• (iv) None of the above
• Answer: (i) Complement
• Explanation: The class of Deterministic Context-Free Languages (DCFLs) is closed under complementation. However, it is not closed under union, intersection, or concatenation.

1. (e) A __ is context free grammar with atmost one non-terminal in the right handside of the production.

• (i) linear grammar
• (ii) linear bounded grammar
• (iii) regular grammar
• (iv) None of the above
• Answer: (i) linear grammar
• Explanation: This is identical to question 1(i) from the 2022 paper. This is the definition of a linear grammar.

1. (f) The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

• (i) Finite state automata
• (ii) Deterministic pushdown automata
• (iii) Non-deterministic pushdown automata
• (iv) Turing machine
• Answer: (i) Finite state automata
• Explanation: Lexical analysis, the first phase of a compiler, involves scanning the source code to identify tokens (keywords, identifiers, operators, etc.). The patterns for these tokens can be described by regular expressions. Regular expressions are recognized by finite automata. Therefore, the power of a finite automaton is both necessary and sufficient for this task.

1. (g) Let L = {w | w in (0+1)* | w has even number of 1s}, i.e., L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

• (i) (0* 1 0* 1)*
• *(ii) 0 (1 0* 1 0) **
• (iii) 0* (1 0* 1)* 0*
• (iv) 0* 1(1 0* 1)* 1 0*
• Answer: (ii) 0* (1 0* 1 0)
• Explanation: We need an expression that allows any number of 0s but ensures 1s always appear in pairs.
  • (i) (0* 1 0* 1)*: This forces every string to end with a 1, which is incorrect (e.g., 01010 is not matched).
  • (ii) 0* (1 0* 1 0*)*: This allows any number of leading 0s. Then, it allows zero or more blocks of (1 0* 1 0*). Each block contains exactly two 1s. Any number of 0s can appear between and after the pairs of 1s. This correctly generates all strings with an even number of 1s. For example, 0010100 is matched. 11 is matched. 00 is matched.
  • (iii) This is very similar to (ii) but often written this way too. Let’s analyze 0* (1 0* 1)* 0*. This expression is also correct. (10*1)* generates pairs of 1s separated by 0s. The outer 0*s allow leading and trailing 0s. Let’s compare with (ii). 0* (1 0* 1 0*)* is also correct. Often, there can be multiple correct regular expressions. In this set of choices, (ii) is a very common and robust representation.
  • (iv) This forces the string to start and end with 1s, which is incorrect.

1. (h) What is the minimum number of states in deterministic finite automata (DFA) for string starting with ba² and ending with a over alphabet {a, b}?

• (i) Ten
• (ii) Nine
• (iii) Eight
• (iv) Six
• Answer: (iv) Six
• Explanation: The language is L = {w | w starts with baa and ends with a}. The minimal string is baa. The language is baa(a+b)*a. Let’s design the minimal DFA:
  • q0: Start state
  • q1: Seen b
  • q2: Seen ba
  • q3: Seen baa (This is an accepting state, as baa is in L)
  • q4: Have a valid prefix baa... but the last symbol seen was b.
  • q_dead: A trap state for invalid prefixes (e.g., starts with a).
    Transitions:
  • δ(q0, b) = q1, δ(q0, a) = q_dead
  • δ(q1, a) = q2, δ(q1, b) = q_dead
  • δ(q2, a) = q3, δ(q2, b) = q_dead
  • δ(q3, a) = q3 (ends in aa, which is fine)
  • δ(q3, b) = q4 (ends in ab, not accepting)
  • δ(q4, a) = q3 (ends in ba, accepting)
  • δ(q4, b) = q4 (ends in bb, not accepting)
  • Any transition from q_dead goes to q_dead.
    The reachable states are {q0, q1, q2, q3, q4, q_dead}. This is a total of 6 states.

1. (i) The decision problem is the function from string to _

• (i) char
• (ii) int
• (iii) boolean
• (iv) None of the above
• Answer: (iii) boolean
• Explanation: A decision problem is a problem that can be posed as a yes-or-no question of the input values. The output is a single boolean value: true (yes) or false (no).

1. (j) A language L may not be accepted by a turing machine if

• (i) it is recursively enumerable
• (ii) it is recursive
• (iii) L can be enumerated by some turing machine
• (iv) None of the above
• Answer: (iv) None of the above
• Explanation: The question asks for a condition under which a language might not be accepted.
  • (i) A language is recursively enumerable (RE) if and only if it is accepted by a Turing machine. So this is a condition for acceptance.
  • (ii) Recursive languages are a subset of RE languages, so they are also accepted by a Turing machine (one that always halts).
  • (iii) A language can be enumerated if and only if it is RE. So this is also a condition for acceptance.
    Since all three options describe languages that are accepted by a Turing machine, none of them are correct answers to the question. The only logical choice is “None of the above”. A language that is not recursively enumerable (e.g., the complement of the halting problem) cannot be accepted by a Turing machine.