Time Left - 15:00 mins
GATE Prev Year : Theory of Computation Test-5
Attempt now to get your rank among 490 students!
Question 1
Consider the following two statements:
S1: {02n|n≥ 1} is a regular language
S2: {0m1n0m+n|m ≥ 1 and n ≥ 1} is a regular language
Which of the following statements is correct?
S1: {02n|n≥ 1} is a regular language
S2: {0m1n0m+n|m ≥ 1 and n ≥ 1} is a regular language
Which of the following statements is correct?
Question 2
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least
Question 3
L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as ω1, ω2, ω3, …… define another language L2 over Σ ∪ {#} as {ωi # ωj : ωj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.
S1 : L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive
Which of the following statements is true?
S1 : L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive
Which of the following statements is true?
Question 4
Consider two languages L1 and L2, each on the alphabet Σ. Let f: Σ → Σ be a polynomial time computable bijection such that (∀x)[x∈ L1 iff f(x) ∈L2]. Further, let f–1be also polynomial time computable.
Which of the following CANNOT be true?
Which of the following CANNOT be true?
Question 5
Consider the grammar
E → E + n | E × n | n
For a sentence n + n × n, the handles in the right-sentential form of the reduction are
E → E + n | E × n | n
For a sentence n + n × n, the handles in the right-sentential form of the reduction are
Question 6
Consider the languages
L1 = {wwR |w
{0, 1}*}
L2 = {w # wR | w
{0, 1}*}, where # is a special symbol
L3 = {ww| w
(0, 1}*)
Which one of the following is TRUE?
L1 = {wwR |w
{0, 1}*} L2 = {w # wR | w
{0, 1}*}, where # is a special symbol L3 = {ww| w
(0, 1}*) Which one of the following is TRUE?
- 490 attempts
- 1 upvote
- 11 comments
Nov 14GATE & PSU CS
