# Questions tagged [theory]

The tag has no usage guidance.

46 questions
Filter by
Sorted by
Tagged with
37 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&...
45 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
32 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&...
31 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 ...
28 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
24 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, ...
88 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
41 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 ...
46 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 ...
29 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-...
27 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? ...
• 125
14 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
32 views

1k 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.
40 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
5k 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 ...
589 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 ...
84 views

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
88 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,369
1 vote
380 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 ...
• 11
6k 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