Questions tagged [theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
2 answers
84 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
369 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
0 answers
41 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
0 answers
40 views

How does a Turing machine work when the current head location is at the right end of its configuration?

Let's say we have a Turing Machine M1 and we have following two cases: (1) Left end of tape a,b,c are part of "tape alphabet" and u,v are some string constructed from "tape alphabet&...
0 votes
1 answer
203 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 ...
1 vote
1 answer
199 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&...
0 votes
1 answer
72 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 ...
-2 votes
1 answer
44 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 ...
1 vote
1 answer
133 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, ...
2 votes
2 answers
95 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 ...
1 vote
1 answer
111 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 ...
0 votes
1 answer
92 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
52 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
28 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? ...
  • 123
0 votes
0 answers
19 views

Can anyone here recommend me some Constructing PDA problems?

The type of problems I am trying to practice is cobstructing a pda that will help me learn a lot. I need some tricky questions not the easy straightforward ones. Like L=a^mb^na^nb^m m+n=n+m Or using 2 ...
1 vote
0 answers
38 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,...
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
46 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
85 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 ...
0 votes
1 answer
18 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
251 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 ...
  • 105
0 votes
2 answers
35 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
416 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 vote
0 answers
57 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
36 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 ...
  • 937
1 vote
3 answers
73 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
150 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
47 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
68 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 ...
1 vote
1 answer
37 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 ...
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 ...
3 votes
0 answers
40 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
165 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
37 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
379 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 ...
user avatar
0 votes
2 answers
63 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
48 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 ...
-3 votes
1 answer
2k 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
48 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
7 votes
3 answers
6k views

Why does a DFA have multiple final states?

I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple ...
3 votes
4 answers
668 views

Are all computer viruses man-made?

I'm curious if the origin of any successful computer virus is known to NOT have an intentional, human originator. To put it another way, do computer viruses ever "spontaneously" originate through the ...
user avatar
0 votes
1 answer
93 views

Mcculloch and Pitts Neurons: Is there errata in this article?

The paper A LOGICAL CALCULUS OF THE IDEAS IMMANENT IN NERVOUS ACTIVITY has the following description of neurons, which I question if there is errata or perhaps I need more information to understand ...
  • 175
6 votes
1 answer
97 views

Is there such a notion as "effectively computable reductions" or would this be not useful

Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...
  • 1,429
1 vote
0 answers
426 views

Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?

My textbook states: Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
17 votes
2 answers
7k views

Can a deterministic finite automaton ever go into an infinite loop?

As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.
  • 171
3 votes
1 answer
116 views

NFA equality for automata with partial transition functions and all states accepting

Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in ...
  • 577