Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for gate1997+theory-of-computation
64
votes
8
answers
1
GATE CSE 1997 | Question: 6.4
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring? $0^*(1+0)^*$ $0^*1010^*$ $0^*1^*01^*$ $0^*(10+1)^*$
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring?$0^*(1+0)^*$$0^*1010^*$$0^*1^*01^*$$...
Kathleen
37.2k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
regular-expression
normal
+
–
38
votes
5
answers
2
GATE CSE 1997 | Question: 3.4
Given $\Sigma=\{a,b\}$, which one of the following sets is not countable? Set of all strings over $\Sigma$ Set of all languages over $\Sigma$ Set of all regular languages over $\Sigma$ Set of all languages over $\Sigma$ accepted by Turing machines
Given $\Sigma=\{a,b\}$, which one of the following sets is not countable?Set of all strings over $\Sigma$Set of all languages over $\Sigma$Set of all regular languages ov...
Kathleen
12.2k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
normal
countable-uncountable-set
+
–
21
votes
2
answers
3
GATE CSE 1997 | Question: 70
Following is a state table for time finite state machine. ... . For example if states $X$ and $Y$ are equivalent then use $XY$ as the name for the equivalent state in the minimal machine).
Following is a state table for time finite state machine.$$\begin{array}{|l|ll|}\hline \textbf{Present State} & \textbf{Next State Output} \\ & \textbf{Input- 0} & \t...
go_editor
7.7k
views
go_editor
asked
Oct 14, 2015
Theory of Computation
gate1997
theory-of-computation
minimal-state-automata
descriptive
+
–
41
votes
3
answers
4
GATE CSE 1997 | Question: 21
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where $L^P = \left\{s \mid ss' \in L \text{ some string }s'\right\}$ $L^R = \left\{s \mid s \text{ obtained by reversing some string in }L\right\}$
Given that $L$ is a language accepted by a finite state machine, show that $L^P$ and $L^R$ are also accepted by some finite state machines, where$L^P = \left\{s \mid ss' ...
Kathleen
5.2k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
finite-automata
proof
+
–
25
votes
4
answers
5
GATE CSE 1997 | Question: 6.6
Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata? $\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$ $\left\{ ww^R \mid w \in \{a,b,c\}^*\right\}$ ... $w^R$ is the string obtained by reversing $'w'$.
Which of the following languages over $\left\{a,b,c\right\}$ is accepted by a deterministic pushdown automata?$\left\{ wcw^R \mid w \in \left\{a,b\right\}^*\right\}$$\lef...
Kathleen
10.6k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
pushdown-automata
easy
+
–
34
votes
4
answers
6
GATE CSE 1997 | Question: 6.5
Which one of the following is not decidable? Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ steps Equivalence of two given Turing machines Language accepted by a given finite state machine is not empty Language generated by a context free grammar is non-empty
Which one of the following is not decidable?Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ stepsEquivalence of two given Turing m...
Kathleen
9.9k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
decidability
easy
+
–
25
votes
4
answers
7
GATE CSE 1997 | Question: 11
Consider the grammar $S \rightarrow bSe$ $S \rightarrow PQR$ $P \rightarrow bPc$ $P \rightarrow \varepsilon$ $Q \rightarrow cQd$ $Q \rightarrow \varepsilon$ $R \rightarrow dRe$ $R \rightarrow \varepsilon$ where $S, P, Q, R$ ... $i, j, k, m$? Find the smallest string that has two parse trees.
Consider the grammar$S \rightarrow bSe$$S \rightarrow PQR$$P \rightarrow bPc$$P \rightarrow \varepsilon$$Q \rightarrow cQd$$Q \rightarrow \varepsilon$$R \rightarrow dRe...
Kathleen
6.4k
views
Kathleen
asked
Sep 29, 2014
Compiler Design
gate1997
compiler-design
grammar
normal
theory-of-computation
descriptive
+
–
24
votes
1
answer
8
GATE CSE 1997 | Question: 20
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$'s is divisible by three.
Construct a finite state machine with minimum number of states, accepting all strings over $(a,b)$ such that the number of $a$'s is divisible by two and the number of $b$...
Kathleen
14.3k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
finite-automata
normal
minimal-state-automata
descriptive
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register