1
GATE CSE 2014 Set 2
+2
-0.6
Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_2} = \left\{ {w \in \left\{ {0,\,\,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(000)'s$$ as $$(111)'s$$$$\left. \, \right\}$$. Which one of the following is TRUE?
A
$${L_1}$$ is regular but not $${L_2}$$
B
$${L_2}$$ is regular but not $${L_1}$$
C
Both $${L_1}$$ and $${L_2}$$ are regular
D
Neither $${L_1}$$ nor $${L_2}$$ are regular
2
GATE CSE 2014 Set 2
+2
-0.6
Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_2} = \left\{ {w \in \left\{ {0,\,\,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(000)'s$$ as $$(111)'s$$$$\left. \, \right\}$$. Which one of the following is TRUE?
A
$${L_1}$$ is regular but not $${L_2}$$
B
$${L_2}$$ is regular but not $${L_1}$$
C
Both $${L_1}$$ and $${L_2}$$ are regular
D
Neither $${L_1}$$ nor $${L_2}$$ are regular
3
GATE CSE 2014 Set 2
+1
-0.3
Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?
A
If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursive then $$A$$ is recursive.
B
If $$A\,\,{ \le _m}\,\,B$$ and $$A$$ is undecidable then $$B$$ is un-decidable.
C
If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursively enumerable then $$A$$ is recursively enumerable.
D
If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is not recursively enumerable then $$A$$ is not recursively enumerable.
4
GATE CSE 2014 Set 2
+2
-0.6
Let $$< M >$$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.}$$
Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machine that accepts a string of length $$\left. {2014} \right\}.$$ Then, $$L$$ is
A
decidable and recursively enumerable
B
un-decidable but recursively enumerable
C
un-decidable and not recursively enumerable
D
decidable but not recursively enumerable
GATE CSE Papers
2023
2022
2020
2019
2018
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Medical
NEETAIIMS