User Peter Leupold

4 votes

Accepted

Which are the cases where the "pumping lemma" doesn't work?

answered Jun 22, 2017 at 11:45

4 votes

Accepted

Meaning of $|w| ≡ 2 \mod 3$

answered Nov 3, 2017 at 11:20

3 votes

Accepted

Turing machine - compare two words

answered Apr 25, 2019 at 13:11

3 votes

Why is BNF considered an unsatisfactory technique for describing a language?

answered May 29, 2016 at 4:50

3 votes

Accepted

Algorithm for checking unambiguity in the derivation of a string

answered Oct 6, 2016 at 5:21

3 votes

Can there be an algorithm for a relation which is not a function?

answered Jan 18, 2017 at 11:13

2 votes

Accepted

Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

answered Jun 26, 2016 at 10:51

2 votes

Misconception in taking Pumping Length of language {a} to be $2$

answered Mar 9, 2016 at 10:44

2 votes

Accepted

Pumping-Lemma regular languages: Consider multiple cases?

answered Dec 18, 2017 at 14:38

2 votes

Why is NP-hard not necessarily NP?

answered Apr 19, 2017 at 8:06

2 votes

Constructing a decider for a language

answered Oct 30, 2017 at 10:13

1 vote

Accepted

Pumping lemma for context-free languages - Am I doing it right?

answered Oct 26, 2017 at 14:02

1 vote

Accepted

Find biggest K, such that any subset of size less than K is not affecting the array

answered Nov 16, 2017 at 14:41

1 vote

Is the halting problem solvable for NPDAs?

answered May 30, 2019 at 17:53

1 vote

Accepted

Find a grammar for this language

answered Nov 15, 2018 at 12:27

1 vote

When are two CFG's different?

answered Apr 9, 2019 at 10:05

1 vote

Is there a known method for constructing a grammar given a finite set of finite strings?

answered Mar 9, 2016 at 11:48

1 vote

Can one consider living (biological) cell to be Turing Complete?

answered Apr 5, 2016 at 11:24

1 vote

What is the closest result relating perfect shuffle closure of primitive words?

answered May 20, 2016 at 11:13

1 vote

Is there a standard (common) notation for the following operation on binary strings?

answered May 21, 2016 at 14:13

1 vote

Accepted

Order classic notions of computability by power

answered May 22, 2016 at 6:50

1 vote

Undecidable vs Unsolvable?

answered May 22, 2016 at 15:45

1 vote

Accepted

Proving a grammar/language as not regular

answered Jul 5, 2016 at 15:37

1 vote

Number of nodes of height $h$ in a heap or almost complete binary tree

answered Mar 3, 2017 at 10:47

1 vote

Accepted

How to Trace Path in Proof that Regular Languages are Closed Under Reversal

answered Jun 13, 2016 at 6:13

1 vote

Preservation of context-free languages under prefix and suffix elimination

answered Jun 15, 2016 at 5:03

0 votes

Is there a standard (common) notation for the following operation on binary strings?

answered May 21, 2016 at 5:12

0 votes

What is the expressive power of finite-state transducers and pushdown transducers?

answered May 20, 2016 at 10:54

0 votes

Accepted

Regular grammar with at most one c

answered Mar 10, 2019 at 18:53

0 votes

Accepted

What kind of words does this PDA accepts

answered Nov 2, 2021 at 12:13

Stack Exchange Network

35 Answers

Which are the cases where the "pumping lemma" doesn't work?

Meaning of $|w| ≡ 2 \mod 3$

Turing machine - compare two words

Why is BNF considered an unsatisfactory technique for describing a language?

Algorithm for checking unambiguity in the derivation of a string

Can there be an algorithm for a relation which is not a function?

Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

Misconception in taking Pumping Length of language {a} to be $2$

Pumping-Lemma regular languages: Consider multiple cases?

Why is NP-hard not necessarily NP?

Constructing a decider for a language

Pumping lemma for context-free languages - Am I doing it right?

Find biggest K, such that any subset of size less than K is not affecting the array

Is the halting problem solvable for NPDAs?

Find a grammar for this language

When are two CFG's different?

Is there a known method for constructing a grammar given a finite set of finite strings?

Can one consider living (biological) cell to be Turing Complete?

What is the closest result relating perfect shuffle closure of primitive words?

Is there a standard (common) notation for the following operation on binary strings?

Order classic notions of computability by power

Undecidable vs Unsolvable?

Proving a grammar/language as not regular

Number of nodes of height $h$ in a heap or almost complete binary tree

How to Trace Path in Proof that Regular Languages are Closed Under Reversal

Preservation of context-free languages under prefix and suffix elimination

Is there a standard (common) notation for the following operation on binary strings?

What is the expressive power of finite-state transducers and pushdown transducers?

Regular grammar with at most one c

What kind of words does this PDA accepts