Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Webpage for Theory of Computation:
Recent questions tagged theory-of-computation
1
votes
0
answers
61
Turing machines question(Turing machine for time travelling
Imagine a Turing machine that needs to determine whether a computation will halt or continue when provided with a specific input. However, there's a twist: the Turing machine has the ability to send messages backward in ... is generated by ChatGPT, still it is interesting whether it is possible to design the turing machine or not?
Imagine a Turing machine that needs to determine whether a computation will halt or continue when provided with a specific input. However, there's a twist: the Turing mac...
rajveer43
120
views
rajveer43
asked
Dec 2, 2023
Theory of Computation
theory-of-computation
query
+
–
0
votes
0
answers
62
Are Mealy and Moore Machines are there in the Gate 2024 Syllabus?
rajveer43
119
views
rajveer43
asked
Nov 30, 2023
Theory of Computation
theory-of-computation
syllabus
query
+
–
0
votes
1
answer
63
Not Regular language [find out]
Why is C is regular as it non regular as? Please help me with this confusion
Why is C is regular as it non regular as?Please help me with this confusion
Deepak9000
201
views
Deepak9000
asked
Nov 27, 2023
Theory of Computation
finite-automata
theory-of-computation
regular-language
+
–
0
votes
1
answer
64
Test Series: Is null string considered as a proper prefix of any string? According to me, total number of proper prefixes for n length string should be (n-1), can anyone please get this point cleared.
tishhaagrawal
236
views
tishhaagrawal
asked
Nov 26, 2023
Theory of Computation
test-series
theory-of-computation
gate-preparation
general-topic-doubt
+
–
0
votes
1
answer
65
Gate 2015 set1
What is meaning of " L is recursively enumerable but not recursive " ?
What is meaning of " L is recursively enumerable but not recursive " ?
shubhamP
185
views
shubhamP
asked
Nov 25, 2023
Theory of Computation
theory-of-computation
gatecse-2015-set1
+
–
0
votes
1
answer
66
Regular grammar
Çșȇ ʛấẗẻ
172
views
Çșȇ ʛấẗẻ
asked
Nov 22, 2023
Theory of Computation
theory-of-computation
regular-grammar
finite-automata
+
–
0
votes
1
answer
67
Made easy TOC
Given L1 = {a*baa*} and L2 = {ab*} The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
Given L1 = {a*baa*} and L2 = {ab*}The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by
amitarp818
223
views
amitarp818
asked
Nov 18, 2023
Theory of Computation
made-easy-test-series
theory-of-computation
test-series
+
–
1
votes
2
answers
68
Ace Test series
Which of the following Language has Prefix property? A) L=01* B) L=0*1* c) L= {0" 1" | n>, 1} D) L= {WW | We(0+1)*}
Which of the following Language has Prefix property?A) L=01*B) L=0*1*c) L= {0" 1" | n>, 1}D) L= {WW | We(0+1)*}
amrish0524
269
views
amrish0524
asked
Nov 14, 2023
Theory of Computation
theory-of-computation
ace-test-series
+
–
0
votes
0
answers
69
Michael Sipser Decidability Problem
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. L = {M | M is a Turing machine and L(M) ∈ TIME(2^n)}
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
baofbuiafbi
141
views
baofbuiafbi
asked
Nov 14, 2023
Theory of Computation
theory-of-computation
time-complexity
michael-sipser
+
–
0
votes
0
answers
70
Michael Sipster Decidability Problems
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
baofbuiafbi
142
views
baofbuiafbi
asked
Nov 14, 2023
Theory of Computation
theory-of-computation
michael-sipser
algorithms
+
–
0
votes
0
answers
71
Michael Sipster Theory of Computation
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.
baofbuiafbi
151
views
baofbuiafbi
asked
Nov 14, 2023
Theory of Computation
theory-of-computation
number-of-dfa
michael-sipser
+
–
0
votes
0
answers
72
Pumping Lemma
If there is a w’ such that w’ ∉ L in the final step of pumping lemma, then L is not regular (Lemma fails) Can we conversely say for certain if L is not regular, then definitely there is a w’ ∉ L. Simply : Can there be a case where we have all w’ ∈ L and still language is not regular?
If there is a w’ such that w’ ∉ L in the final step of pumping lemma, then L is not regular (Lemma fails)Can we conversely say for certain if L is not regular, then...
Mrityudoot
133
views
Mrityudoot
asked
Nov 8, 2023
Theory of Computation
theory-of-computation
pumping-lemma
regular-language
+
–
1
votes
0
answers
73
Language to PDA
Design the Push down Automata for the language L={anbmc2nd3m,n,m>=1}.Check the acceptance string by both the empty stack and final state method.
Design the Push down Automata for the language L={anbmc2nd3m,n,m>=1}.Check the acceptance string by both the empty stack and final state method.
alexmurugan
334
views
alexmurugan
asked
Nov 3, 2023
Theory of Computation
theory-of-computation
pushdown-automata
+
–
0
votes
0
answers
74
Turing machine for a^n b^m c^n d^m NET UGC December 2022
The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back in ... it wrong by skipping one state and directly looping back to 'q0' Please shed some light on it, thanks!
The state diagram for the initial part of this turing machine given as:Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' ...
Picturesque
236
views
Picturesque
asked
Oct 31, 2023
Theory of Computation
theory-of-computation
turing-machine
+
–
0
votes
2
answers
75
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)^*$
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)^*$
Pratik.patil
369
views
Pratik.patil
asked
Oct 30, 2023
Theory of Computation
theory-of-computation
ace-test-series
regular-expression
+
–
3
votes
2
answers
76
TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
Jiten008
343
views
Jiten008
asked
Oct 24, 2023
Theory of Computation
pushdown-automata
theory-of-computation
self-doubt
regular-language
context-free-language
context-sensitive
turing-machine
closure-property
context-free-grammar
+
–
0
votes
0
answers
77
MADE EASY TS
here option PRIME is recursive , but why FACTOR is not regular, my approach is { here n,a,b all are distinct and n has the range bew [a,b] and we know if range is defined then regularity is possible. PRIME AND REGULAR ARE FACTOR NAME.
here option PRIME is recursive , but why FACTOR is not regular,my approach is { here n,a,b all are distinct and n has the range bew [a,b] and we know if range is defi...
jugnu1337
291
views
jugnu1337
asked
Oct 22, 2023
Theory of Computation
theory-of-computation
made-easy-test-series
+
–
0
votes
1
answer
78
#Regular Languages
For a particular input, a turing machine can ‘hang’ on encountering an infinite loop. Why can’t we say the same for any other machine? i.e A DFA or NFA that follows say a*(b). Will the automaton not ‘hang’ if a string $a^n$ where $n \to$ ∞ is fed to it? Isn’t ‘never accepting but progressing’ the same as hanging?
For a particular input, a turing machine can ‘hang’ on encountering an infinite loop. Why can’t we say the same for any other machine? i.e A DFA or NFA that follows...
Mrityudoot
319
views
Mrityudoot
asked
Oct 21, 2023
Theory of Computation
theory-of-computation
regular-expression
finite-automata
regular-language
+
–
0
votes
1
answer
79
Automata and Formal Languages
jam
210
views
jam
asked
Oct 17, 2023
Theory of Computation
theory-of-computation
finite-automata
+
–
0
votes
1
answer
80
#syallabus completion
HELLO SIR , SIR I HAVE LEFT WITH TOC, CD , DM AND CN AND I THOUGHT , I SHOULD LEAVE ANY TWO OF THESE SO THAT I CAN FOCUS ON REVISION PROPERLY… SO , I WANT TO KNOW THAT WHICH 2 OF THESE SHOULD LEFT ASIDE .
HELLO SIR , SIR I HAVE LEFT WITH TOC, CD , DM AND CN AND I THOUGHT , I SHOULD LEAVE ANY TWO OF THESE SO THAT I CAN FOCUS ON REVISION PROPERLY… SO , I WANT TO KNOW THAT ...
jaswinder
195
views
jaswinder
asked
Oct 12, 2023
GATE
out-of-gate-syllabus
discrete-mathematics
theory-of-computation
computer-networks
compiler-design
goclasses
+
–
1
votes
1
answer
81
Checking regularity of a given language.
$L =\left \{ w(w^{R})^{*}: w\in(a,b)^{*} \right \}.$ Is this language regular?
$L =\left \{ w(w^{R})^{*}: w\in(a,b)^{*} \right \}.$Is this language regular?
rexritz
234
views
rexritz
asked
Oct 8, 2023
Theory of Computation
theory-of-computation
regular-language
+
–
0
votes
1
answer
82
Made easy test series
Please explain the why A and D are correct?
Please explain the why A and D are correct?
Rohit Chakraborty
434
views
Rohit Chakraborty
asked
Oct 5, 2023
Theory of Computation
theory-of-computation
regular-expression
number-of-dfa
made-easy-test-series
+
–
0
votes
0
answers
83
10. Give the translation scheme that converts infix to postfix form for the following grammar. Also generate the annotated parse tree for input string 2+6+1 E-> E+T E->T T->0|1|2|3|4|5|6|7|8|9
Give the translation scheme that converts infix to postfix form for the following grammar. Also generate the annotated parse tree for input string 2+6+1E- E+TE->TT->0|1|2...
ahmed65956
583
views
ahmed65956
asked
Sep 27, 2023
Compiler Design
syntax-directed-translation
computer-networks
packet-switching
routing
theory-of-computation
+
–
1
votes
0
answers
84
Let P,Q and R be regular expressions such that the number of strings generated by P is p, Q is q and R is r. What is the number of strings generated by the regular expression (P+R)*Q+PQ?
krati_ag19
321
views
krati_ag19
asked
Sep 22, 2023
Theory of Computation
theory-of-computation
regular-expression
+
–
Page:
« prev
1
2
3
4
5
6
7
8
...
155
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register