Computer Science
reinierpost
Meta user
Network profile
Summary Answers Questions Tags Badges Favorites Bounties Reputation All actions

95 Answers

Newest Activity Votes
27
Why do pushdown automata use a stack?
Oct 23 '18 at 20:58
18
on “On the cruelty of really teaching computing science”
Aug 8 '16 at 20:32
13
Theoretical machines which are more powerful than Turing machines
Apr 5 '16 at 17:21
12
Is language equality for linear context-free grammars decidable?
May 12 '16 at 18:49
9
Why are regular expressions defined with union, concatenation and star operations?
May 28 '16 at 22:42
8
What parts of a programming language can't be defined using Regular Expressions?
Jan 8 '18 at 22:36
7
I think you can always compress compressed data, is it true?
Nov 24 '18 at 9:05
6
What is an IELR(1)-parser?
Dec 5 '12 at 12:01
6
Can a petri net fire only one transition at a single moment?
Nov 9 '14 at 0:40
6
Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”?
Jan 18 '19 at 15:49
6
Converting context-free grammar to chomsky normal form
Sep 19 '16 at 22:04
6
Design patterns for simple text based scripting language?
Feb 25 '16 at 23:41
6
How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)
Feb 16 '16 at 18:52
6
Is the language of Roman numerals ambiguous?
Jan 6 '13 at 16:12
6
What is the point of (Compactness theorem in the) Overspill principle?
Apr 21 '14 at 13:38
6
How to prove that a grammar is unambiguous?
Jun 11 '12 at 8:35
5
Parikh's Theorem: CFL's “contain” regular languages?
Apr 3 '18 at 16:02
5
What type of an algorithm is being used for directory structure scanning?
May 25 '16 at 7:55
5
Is there a physical analogy to the Turing Machine?
Dec 10 '14 at 10:03
5
How did the word “production” end up being a synonym with the word “rule” in the context of Computer Science?
Dec 15 '16 at 11:12
5
Why is the set of all regular expressions classified as context-free, instead of regular?
Nov 18 '15 at 8:43
5
How is the number of states in a Turing machine bounded?
Nov 7 '14 at 10:14
4
What is language density used for?
Mar 5 '19 at 22:43
4
Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?
May 10 '19 at 8:58
4
Why is non-determinism a useful concept?
Mar 12 '14 at 23:49
4
Is there a way a proving a language regular/non-regular that works for every possible language?
Feb 27 '19 at 19:05
4
Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL
Dec 13 '17 at 11:10
4
Are Epsilon-NFAs a way to make designing NFAs easier?
Sep 14 '17 at 18:01
4
Infinite Language vs. finite language
Nov 12 '12 at 16:08
4
What is the average time complexity, for a single linked list, for performing an insert?
Oct 8 '15 at 16:04
1 2 3 4