Questions tagged [theory]
The theory tag has no usage guidance.
60 questions
2
votes
0
answers
61
views
How to prove that if L is a regular language, then f(L) is also a regular language?
If $f$ is a function of integers, define $f(L)$ as:
$$
f(L) = \{w \mid \text{for some } x, \text{ where } |x| = f(|w|), \, wx \in L \}.
$$
This means $f(L)$ is the set of strings $w$ such that there ...
- 21
-2
votes
0
answers
26
views
Consider the language SUBSETDFA={⟨M1,M2⟩|L(M1)⊆L(M2)} . Show that SUBSETDFA is decidable
Consider the language SUBSET-DFA={⟨M1,M2⟩|L(M1)⊆L(M2)}
. Show that SUBSETDFA
is decidable.
- 1
1
vote
0
answers
34
views
Caching terminology
In docs sites, blogs, tools and on StackExchange, I often see various caching terms used interchangeably (though I suspect they differ).
Is there a theoretical difference between these terms:
...
- 111
16
votes
2
answers
2k
views
What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?
This question has been bugging me ever since I first came across the concept of NP, NP-Complete, and NP-Hard a few years back: what is so fundamental about the polynomial functions that they are used ...
- 261
1
vote
2
answers
228
views
Two Generals' Problem - Thought Experiment
After reading the Two Generals' Problem, I am wondering as to why there isn't any solution and please correct me if I am missing something.
What if, the generals decide that they will attack if they ...
- 111
0
votes
1
answer
26
views
Are there any example of practical application of counter machines?
I am currently working on a presentation over how counter machines are as effective as Turing machines. During my research, I found out that random access machines are an improved version of counter ...
2
votes
0
answers
79
views
Theoretical origin of acquire semantics only for reads?
What theoretical concept lies behind the strong restriction of acquire semantics - to reads, and release semantics - to writes? (With papers titles and authors, if possible.)
Is it related to ...
- 171
0
votes
0
answers
129
views
For an NFA with langauge: {w ∈ {0, 1}*: the length of w is odd but not a multiple of three}. How many states are required?
For an NFA with language: {w ∈ {0, 1}*: the length of w is odd but not a multiple of three}. How many states are required?
This is the work I have come up with so far:
q0: non-accepting state - ...
- 1
2
votes
1
answer
53
views
Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular
There is an exercise in a book about finite automata that I couldn't solve:
Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular either, using the fact that REG is ...
- 1,624
-4
votes
1
answer
61
views
Turing Machine Decidability [closed]
Consider the language $L = \{\langle M_1,\ M_2 \rangle \mid \exists x : x \in L(M_1) \cap L(M_2)\}$. Show that $L$ is not decidable.
I'm attempting a proof by contradiction but I'm having trouble with ...
- 1
6
votes
1
answer
316
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 ...
- 83
0
votes
2
answers
112
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
1
vote
0
answers
42
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
287
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 ...
2
votes
2
answers
443
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 (...
- 43
0
votes
3
answers
6k
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: $(...
- 43
1
vote
1
answer
186
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
2k
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 ...
- 335
1
vote
1
answer
5k
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&...
- 335
0
votes
1
answer
3k
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 ...
- 335
-2
votes
1
answer
141
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 ...
- 335
1
vote
1
answer
778
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, ...
- 335
2
votes
2
answers
247
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 ...
- 335
1
vote
1
answer
385
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 ...
- 335
0
votes
1
answer
250
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
99
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? ...
1
vote
0
answers
66
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
6k
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
48
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
783
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
54
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
272
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 ...
- 99
0
votes
2
answers
50
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
4
votes
1
answer
1k
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,154
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
1
vote
4
answers
118
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
326
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
76
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
74
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
68
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
119
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
49
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
88
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
356
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
40
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
394
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
96
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
73
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