Questions tagged [theory]
The theory tag has no usage guidance.
57
questions
-2
votes
0
answers
32
views
Turning machines
Consider the language L = {<M1 , M2> | Ǝx such that x ∈ L(M1) ∩ L(M2)} Show that L is not decidable.
Im doing a proof by contradiction but im having trouble with the turning machine part
- 1
1
vote
0
answers
26
views
Is there any reference materials on complexity analysis for lazy languages?
Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell?
I know how laziness is implemented and how it can be expanded and ...
5
votes
1
answer
129
views
How do I improve my problem-solving and creative thinking skills in Computer Science?
I am a CS undergrad trying to improve my problem-solving skills. I have noticed that I have a problem with theoretical computer science which I've been trying to fix largely unsuccessfully till now. I ...
- 51
0
votes
0
answers
32
views
What are the applications of Belief Revision?
In my Computer Science graduation, I came across this concept of Belief Revision, which focus on knowledge representation and the possible operations that can be done with the facts that a "...
- 103
0
votes
2
answers
59
views
Can negative edge weights in a graph be positive numbers?
I'm a little confused by the concept of a "negative" edge weight. All of the examples I have seen represent negative edge weights as negative numbers. Is it possible for an edge weight to ...
- 149
0
votes
0
answers
50
views
Enumerating Turing Machine (a,b)*
What does it mean to make an enumerating Turing machine of (a,b)*, since it has so many possibilities as to what the string can be. Do I just pick some random string and enumerate it like aab?
- 1
1
vote
0
answers
37
views
Which non regular language meets the requirements for pumping lemma for regular languages?
I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
0
votes
1
answer
121
views
Why Regular Grammar is Left/Right Linear?
From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules)
But, my question is why it is mandatory?
Can't we ...
0
votes
1
answer
33
views
turing machine to add each number with the one next to it
im trying to make a turing machine that adds a number with the one next to it on the right. and after, it replaces that number with the result of the addition.
for example if input is 1012, 1+0=1 (...
- 1
-5
votes
1
answer
400
views
regex for {w ϵ {a,b}*: |w| mod 3 =0}
I think this is what the regular expression would be. (aaa U aab U aba U abb U baa U bab U bba U bbb)*
- 1
2
votes
2
answers
250
views
Intuition for Sipser's proof of PDA to CFG
I understood Sipser's proof of CFG to PDA but I am having a hard time understanding his proof of conversion from PDA to CFG while demonstrating the equivalence between the two.
He splits the proof (...
- 33
0
votes
2
answers
3k
views
Regex for string does not contain the substring "110"
Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)?
Write a regular expression for the language L = {w | w does not contain 110}
So, the answer I get is: $(...
- 33
1
vote
1
answer
119
views
Are there any (theoretical-esque) computer science "competitions" at Undergrad level similar to Putnam?
I have searched for a bit eventually arriving at well known websites like codeforces, atcoder, codewars, codinggame or the various OJs.
They mostly involve solving tasks where usually the main focus ...
- 11
0
votes
1
answer
807
views
How to prove ww^r is context free using pumping lemma for context free languages
I am having a hard time to prove it, what i know is we cannot prove that a language is regular by using pumping lemma cause even if the "pumped string" is in the language the language could ...
- 305
1
vote
1
answer
2k
views
Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?
I understand why L2 is not a regular language. We can use the pumping lemma to prove it
In the case of L2:
assume n = 1 and string = ab
We assume that L2 is regular, so it has "pumping length&...
- 305
0
votes
1
answer
1k
views
When is a grammar ambiguous or When is a grammar not ambiguous?
I was looking at an example of grammar from the website: grammer example
which is as follows:
S → aB / bA
S → aS / bAA / a
B → bS / aBB / b
I believe they forgot to write: A -> a
Next, we are going ...
- 305
-2
votes
1
answer
92
views
How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?
Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method
I end up with this:
My ...
- 305
1
vote
1
answer
434
views
Converting Regular Expression to Finite Automata
I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, ...
- 305
2
votes
2
answers
158
views
Is ε a part of alphabet or property of alphabet and NFA in FA
I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following:
3rd point of the above image is the ...
- 305
1
vote
1
answer
219
views
Converting Deterministic Finite Automata to Regular Expression
I am reading Michael Sipser's "Theory of Computation". In one of the proofs he talks about converting "DFA to Regular Expression" and he talks about "GNFAs". I understand ...
- 305
0
votes
1
answer
187
views
Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable
I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
- 1
0
votes
1
answer
80
views
What does it mean for a machine language to be Turing-complete?
I was reading the Wikipedia article on Turing completeness, but I was having a hard time putting together all of the concepts. In simple terms, what does it mean for an instruction set to have Turing-...
0
votes
0
answers
31
views
Can a complex arrangement of diodes do computation?
If I have a bunch of diodes arranged in some complex, directed graph, can I get it to do computation?
I mean will it add voltages and, for example, as I insert voltage sources in-between the diodes? ...
- 113
1
vote
0
answers
53
views
How to think of states when designing a Turing machine?
I am learning about designing Turing machines and I am struggling when it comes to creating the states diagram, for example if I wanted to design a Turing machine of the language $L=\{a^nb^n, n\geq 0\}...
- 123
10
votes
4
answers
5k
views
Could Gödel’s incompleteness theorem be circumvented with a quine?
As you all probably know, Gödel’s incompleteness theorem states, that it will never be possible for mathematics to prove its own correctness.
Mainly because that proof would be part of mathematics too,...
anon
2
votes
1
answer
1k
views
Can we solve a "very" exponential recurrence?
Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ?
Thanks!
- 29
0
votes
0
answers
47
views
Is this an example of a zero-knowledge proof?
I want to prove to a verifier that I know the passcode of a system. The system contains data/information of the verifier of which is only contained with this system. Since I know the passcode to the ...
- 1
1
vote
1
answer
405
views
If Interpreters are used to run code and are written in another language, won't interpreters need interpreters?
As I was going through my online lectures, it is stated that python is interpreted with Cpython, a software written in C. Similarly, they have Jython (written in Java) and PyPy (written in Python). My ...
- 13
0
votes
1
answer
37
views
Same instances for different problems
According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?).
So, two problems may ...
- 103
-4
votes
1
answer
260
views
Must a partial halt decider be a pure function of its inputs?
Must a partial halt decider be a pure function of its inputs?
A partial halt decider correctly decides the halt status of some of its inputs.
I am trying to write C code that would be acceptable to ...
- 87
0
votes
2
answers
38
views
Existence of infinite unique FSAs
It is reasonably simple to show that there are an infinite number of different finite state automata that can be constructed, but has it been proven if there is an infinite number of unique finite ...
- 3
3
votes
1
answer
847
views
Can a non deterministic finite automaton go into infinite loop?
Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
- 1,112
1
vote
0
answers
60
views
Could someone explain the algorithm from this paper? (Thank you) [closed]
Trying to get a fair understanding of our artificial immune systems. To do this I’ve been reviewing this paper, but the algorithm and mathematics is over my head, could someone explain the below to me ...
- 11
0
votes
0
answers
38
views
What is the name of this data structure?
I am trying to solve a problem efficiently.
The problem is to recurse over a set $\{0,1,\dots,n-1\}$ (as array) in ascending or descending order, while removing or re-adding items in $O(1)$ time.
A ...
- 957
1
vote
3
answers
77
views
Should I be a good computer scientist to become a great software developer?
As I am headed into a Computer Science major wishing to eventually become a software developer, I wonder this: should I immerse myself in computer science theory and knowledge (data structures, ...
2
votes
2
answers
251
views
Turing, RAM, or Von Neumann --- which theory/model is the consensus?
I am not a formal student for CS nor have I ever been, I just want to understand something simple about your field for general knowledge, in plea.
Turing, RAM, or Von Neumann --- which theory/model is ...
0
votes
1
answer
54
views
Is memorization necessary in learning computer science?
Backgrounds
Hi guys, I am now trying to teach myself some basic computer science theories. Specifically, I am using the book, CSAPP (computer systems, from a programmer’s perspective) and 15-213 ...
- 1
-1
votes
1
answer
72
views
Is this language a context free language?
Consider the following language, where the alphabet is $\{0, 1, 2\}$:
$B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$.
Is this language a context free language? Prove your answer.
I am ...
- 29
1
vote
1
answer
53
views
Artificial Intelligence: theory vs processing power
It is common to see articles praising the advances in AI (here is one example).
There is no doubt that significant progress has occurred on all kinds of automation, hard games like chess, etc.
The ...
- 111
2
votes
1
answer
113
views
Is the base of natural logarithms $e$ efficiently computable?
Is $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} +\ldots$ efficiently computable? To be more specific, we say that a real number $r$ is efficiently computable if there is a ...
- 21
3
votes
0
answers
44
views
Is there a "theory" of operating systems?
Is there a theory for Operating Systems?
That is, subfields of CS have theoretical parts; i.e. PL has type theory, ML has mathematical theorems, security has a lot of provable properties, etc.
There ...
- 155
1
vote
1
answer
85
views
What's beautiful in CS? [closed]
I'm afraid this may be opinion-based and not apt here, but...
Mathematicians often talk about "mathematical beauty", i.e. Gauss' proof of the Fundamental Theorem of Algebra, Euler's Formula, ...
- 155
0
votes
1
answer
271
views
"If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable."
This is given vertabim in my lecture slides and it seems like I'm having difficulty proving this statement mathematically. I know that P is a subset of NP and NP-Complete is also a subset of NP. But ...
- 1
0
votes
0
answers
38
views
How to get a piece of the Pie? Theoretical Plate Stacking Problem
This is just a theoretical problem that I found in the wild and want to know your solution.
A stack of plates is made between you a cousin and a few others.
Every (4 to 7) many random hours the plate ...
- 1
3
votes
3
answers
382
views
Forest characterization
Prove that each property below characterizes forests...
a. every induced subgraph has a vertex of degree at most one.
When proving a characterization, do we have to prove both directions, like an if ...
user127224
0
votes
2
answers
82
views
string concatenation vs language concatenation
What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure ...
- 13
1
vote
0
answers
67
views
Level Ancestor Query long-paths algorithm complexity of sqrt n
Can someone explain why the complexity of a query for LA is √n when we only decompose the tree into long-paths? How can we show/prove that?
How can we prove that the number of paths can be as high as ...
- 11
0
votes
1
answer
54
views
Consistent theory based on L and not(A->A) is a theorem
I am working on this problem in which I have a theory $T$ based on language $\mathcal{L}$ and the only information we have is that T is consistent and $\vdash \lnot(A \rightarrow A)$. Given this ...
- 109
-3
votes
1
answer
3k
views
DFA that accepts all the strings with exactly two a’s and more than two b’s
It works I checked it but I don't know how to make it smaller :(
the question is in my book,I can solve but it took too much time and effort and I'm pretty sure there's a simple soloution.
0
votes
1
answer
73
views
Shortest unambiguous representation of a graph over an alphabet
I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer:
Given the graph with the matrix ...
- 143