Register

Recent questions and answers in Theory of Computation

3.6k
views
2 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 17 (Page No. 86)
Give an $NFA$ recognizing the language $(01 ∪ 001 ∪ 010)^{*}.$Convert this $NFA$ to an equivalent $DFA.$ Give only the portion of the $DFA$ that is reachable from the start state.
User Avatar
1.1k
views
1 answers
1 votes
Michael Sipser Edition 3 Exercise 1 Question 15 (Page No. 85)
Give a counterexample to show that the following construction fails to prove $\text{Theorem 1.49,}$ the closure of the class of regular languages under the star operation$.$ ... $N$ does not recognize the star of $N_{1}^{'s}$ language.
User Avatar
938
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 14 (Page No. 85)
Show that if $M$ is a $DFA$ that recognizes language $B,$ swapping the accept and not accept states in $M$ yields a new $DFA$ recognizing the ... of languages recognized by $NFA's$ closed under complement$?$ Explain your answer$.$
User Avatar
1.3k
views
1 answers
1 votes
Michael Sipser Edition 3 Exercise 1 Question 13 (Page No. 85)
Let $F$ be the language of all strings over $\{0,1\}$ that do not contain a pair of $1's$ that are separated by an odd number of symbols. Give the state ... helpful first to find a $4$-state $\text{NFA}$ for the complement of $F.)$
User Avatar
870
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 2 (Page No. 83)
Give the formal description of the machines $\text{M1}$ and $\text{M2.}$
User Avatar
860
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 3 (Page No. 83)
The formal description of a $\text{DFA}$ $\text{M}$ is $({q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}),$ where $\text{δ}$ is given by the following table. Give the state diagram of this machine.
User Avatar
1.5k
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 1 (Page No. 83)
The following are the state diagrams of two $\text{DFAs,}$ $\text{M1}$, and $\text{M2.}$ Answer the following questions about each of these machines.What ... accept the string $\text{aabb?}$Does the machine accept the string $\epsilon?$
User Avatar
221
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 0 Question 10 (Page No. 27)
Find the error in the following proof that $2 = 1.$Consider the equation $a = b.$ Multiply both sides by a to obtain $a^{2} = ab.$ Subtract $b^{2}$ from both sides to ... $a$ and $b$ equal $1,$ which shows that $2 = 1.$
User Avatar
387
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 0 Question 8 (Page No. 26)
Consider the undirected graph G= (V, E) where V , the set of nodes, is {1, 2, 3, 4} and E, the set of edges, is {{1, 2}, {2, 3}, {1, 3}, {2 ... . What are the degrees of each node? Indicate a path from node 3 to node 4 on your drawing of G.
User Avatar
305
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 0 Question 7 (Page No. 26)
For each part, give a relation that satisfies the condition.Reflexive and symmetric but not transitiveReflexive and transitive but not symmetricSymmetric and transitive but not reflexive
User Avatar
427
views
2 answers
0 votes
Michael Sipser Edition 3 Exercise 0 Question 4 (Page No. 26)
If A has a elements and B has b elements, how many elements are in A × B? Explain your answer.
User Avatar
367
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 0 Question 2 (Page No. 25)
Write formal descriptions of the following sets.a. The set containing the numbers 1, 10, and 100b. The set containing all integers that are greater than 5c ... abae. The set containing the empty stringf. The set containing nothing at all
User Avatar
532
views
1 answers
1 votes
Michael Sipser Edition 3 Exercise 0 Question 1 (Page No. 25)
Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set.a. {1, 3, 5, 7, . . . }b ... the reverse of w}f. {n| n is an integer and n = n + 1}
User Avatar
84
views
0 answers
0 votes
Regular Expression
Write Regular expression for the set of string over alphabets {a, b} starting with b and ending with odd number of a’s or even number of b’s.
User Avatar
60
views
0 answers
0 votes
DFA construction
construct a minimal DFA for the regular language L= {W | w contain 'a' in every odd position, w∈{a,b}* }
User Avatar
45
views
0 answers
0 votes
DFA
Identify language accepted by following dfa. A. L = {a^n b^m | n,m >= 1} B. L = {a^n b^m | n >= 1, m >= 0} C. L = {a^n b^m | n,m >= 0} D. None
User Avatar
2.9k
views
4 answers
2 votes
GATE CSE 2024 | Set 2 | Question: 52
Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*}\left(a b^{*} a b^{*}\right)^{*}$ ... of string $w$. The number of strings in $L_{2}$ which are also in $L_{1}$ is _________.
User Avatar
43.7k
views
9 answers
56 votes
GATE IT 2004 | Question: 40
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where$K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ ... , (f, \epsilon))\}$.Which one of the following strings is not a member of $L(M)$?$aaa$aabab$baaba$bab$
User Avatar
106
views
0 answers
1 votes
Theory of Computation | Chomsky Hierarchy
A general query,If Regular expression (a+b)* covers the all possible languages over $\sum$= {a,b} then, why we need other type of languages?Are they ... I found these two reasons on internet and nothing else is there any other reasons here?
User Avatar
128
views
1 answers
2 votes
#TOC-regular-language
Captioncreate a DFA for language L={a^n b^m | n=(m%3) } 
User Avatar
207
views
1 answers
0 votes
TOC
Number of states in a DFA that accepts string over the alphabet {0,1} where words start and end with a 1, have even length and every 0 is immediately followed by atleast a 1.
User Avatar
21.0k
views
6 answers
59 votes
GATE CSE 2019 | Question: 48
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ ... $L$ is _______
User Avatar
9.2k
views
4 answers
40 votes
GATE CSE 2005 | Question: 63
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which of the ... complement of the input numberIt increments the input numberit decrements the input number
User Avatar
90
views
0 answers
0 votes
Scoa021 May/June 2023
Draw a DFA and Transition table for the regular expression (a|b)*abb
User Avatar
3.3k
views
3 answers
3 votes
GATE CSE 2024 | Set 2 | Question: 31
Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$ ... {*}\right)(11)^{*}$0^{+}+1(11)^{*}+0(11)^{*}$
User Avatar
3.6k
views
3 answers
5 votes
GATE CSE 2024 | Set 2 | Question: 12
Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below?$0^{*} 1\left(0+10^{*} 1\right)^{*}$0^{*}\left(10^{*} 11\ ... )^{*} 0^{*}$0\left(1+0^{*} 10^{*} 1\right)^{*} 0^{*}$
User Avatar
59
views
0 answers
0 votes
CMI2024-B-02
Let M1 = (Q1, {q1}, ∆1, F1), where ∆1 ⊆ Q1 (Σ ∪ {ϵ}) Q1, be a non-deterministic finite automaton (NFA) accepting a language L1 ⊆ {0, 1} ∗ . Let ϵ denote ... = ϵ and p ′ = q1) Prove or disprove: The language L2 accepted by M2 is L ∗ 1 .
User Avatar
63
views
0 answers
0 votes
CMI 2024-PART B-02.
Let M1 = (Q1, {q1}, ∆1, F1), where ∆1 ⊆ Q1 (Σ ∪ {ϵ}) Q1, be a non-deterministic finite automaton (NFA) accepting a language L1 ⊆ {0, 1} ∗ . Let ϵ ... F1 and a = ϵ and p ′ = q1) Prove or disprove: The language L2 accepted by M2 is L*
User Avatar
192
views
1 answers
0 votes
DFA construction
Design a DFA (Deterministic Finite Automaton) that recognizes the language L defined follows: L= {w -> {a, b}* | every a in w is immediately followed by bb}
User Avatar
268
views
2 answers
2 votes
ISRO 2024
Which f the following statements is FALSE?The intersection of a regular language and a context-free language is context=freeThe intersection of a regular ... -free languages is context-freeThe union of two regular languages is regular
User Avatar
243
views
1 answers
0 votes
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
User Avatar
231
views
1 answers
0 votes
Can
Can $\Sigma^{*}$ be called DCFL? If yes, what would the state transition diagram of its PDA look like?
User Avatar
469
views
3 answers
1 votes
ACE TOC Test
Which of the following regular expression represent the set of all the strings not containing $100$ as a substring ?$0^*(1^*0)^*$0^*1010^*$0^*1^*01^*$0^*(10+1)^*$
User Avatar
12.1k
views
3 answers
20 votes
GATE CSE 2022 | Question: 38
Consider the following languages:$L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$ ... $L_{2} \cap L_{3}$ all are context-free.Neither $L_{1}$ nor its complement is context-free.
User Avatar
469
views
2 answers
0 votes
made easy test series 2023 question
Let r = a(a + b)*, S = aa*b and t = a* b be three regular expressions. Consider the following:Which one of them is correct ?
User Avatar
451
views
3 answers
4 votes
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 62
Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful transition ... mathrm{abbb}^+\mathrm{c}^+\mathrm{c}$a b^* b b(c c)^+$
User Avatar
255
views
1 answers
0 votes
self doubt
How a^i b^j | i !=(2j+1) is dcfl?
User Avatar
349
views
1 answers
1 votes
ISRO 2024
Consider the context-free grammer $G$ below. There $S$ is the starting non terminal symbol, while $a$ and $b$ are terminal symbols.$S \rightarrow aaSb | T$T \ ... $aabbaabb$ does not$aaabb$ belongs to $L(G)$ but $aaaaabbb$ does not
User Avatar
704
views
3 answers
3 votes
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 35
Which of the following strings are a member of the language described by the regular expression $\left(a^* {b} {a}^* b a^* b {a}^*\right)^*$b b b b$bbaaabb$bbaaabbbabb$b b a b b b a b$
User Avatar
To see more, click for all the questions in this category.