User tpm900

4 votes

2 answers

14k views

Does a PDA immediately accept if at final state with empty stack?

asked Feb 28, 2017 at 23:33

4 votes

1 answer

2k views

Every LEFT-RESET Turing machine has an equivalent conventional Turing machine

asked Mar 13, 2017 at 19:27

3 votes

1 answer

639 views

Why does this pumping lemma proof not cover every division of xyz?

asked Feb 6, 2017 at 19:13

2 votes

1 answer

2k views

Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL

asked Mar 2, 2017 at 23:30

2 votes

2 answers

696 views

Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular

asked Feb 9, 2017 at 22:20

2 votes

1 answer

2k views

Pumping Lemma: Is language with equal number of "aa" and "bb" regular?

asked Feb 14, 2017 at 23:14

2 votes

2 answers

2k views

Proof Idea: How to prove the intersection of regular language and CFL is a CFL?

asked Mar 8, 2017 at 1:47

1 vote

1 answer

303 views

Is $A_{PTM}$ a BPP-complete language?

asked May 3, 2017 at 18:01

1 vote

1 answer

4k views

Are there decidable problems that are reducible to undecidable problems?

asked Apr 10, 2017 at 19:25

1 vote

1 answer

296 views

Using amplification lemma to decrease error probability gives 0 as divisor

asked Apr 24, 2017 at 19:10

1 vote

1 answer

225 views

Does a computation tree for a probabilistic Turing machine have to be a binary tree?

asked Apr 25, 2017 at 22:26

1 vote

1 answer

10k views

Pumping Lemma: 1^n^2 is not regular

asked Feb 9, 2017 at 17:35

0 votes

1 answer

561 views

How do I normalize a push down automaton?

asked Mar 3, 2017 at 21:38

0 votes

1 answer

1k views

Is this grammar right associative (why?)

asked Feb 15, 2017 at 19:42

0 votes

0 answers

411 views

Writing a constructive proof for closure of a regular language under homomorphism

asked Feb 19, 2017 at 2:23

0 votes

1 answer

98 views

Prove a language $A_{PTM}$ is not BPP-Complete

asked May 3, 2017 at 17:16

0 votes

2 answers

361 views

Can String be a subtype of Character in a programming language?

asked Apr 17, 2017 at 20:47

Stack Exchange Network

17 Questions

Does a PDA immediately accept if at final state with empty stack?

Every LEFT-RESET Turing machine has an equivalent conventional Turing machine

Why does this pumping lemma proof not cover every division of xyz?

Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL

Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular

Pumping Lemma: Is language with equal number of "aa" and "bb" regular?

Proof Idea: How to prove the intersection of regular language and CFL is a CFL?

Is $A_{PTM}$ a BPP-complete language?

Are there decidable problems that are reducible to undecidable problems?

Using amplification lemma to decrease error probability gives 0 as divisor

Does a computation tree for a probabilistic Turing machine have to be a binary tree?

Pumping Lemma: 1^n^2 is not regular

How do I normalize a push down automaton?

Is this grammar right associative (why?)

Writing a constructive proof for closure of a regular language under homomorphism

Prove a language $A_{PTM}$ is not BPP-Complete

Can String be a subtype of Character in a programming language?