# Tagged Questions

123 views

### Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
110 views

147 views

### Help understand $\text{handle}$ in parsing problem

The BNF is defined as followed: S -> aAb | bBA A -> ab | aAB B -> bB | b The sentence is: aaAbBb And this is the ...
169 views

### Need help explain BNF

I have several BNF defined as follow: ...
125 views

### Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet {0,1}?

Do there exists permutations $\pi_1,\pi_2$ and polynomial size CFG that describe the finite language {$w \pi_1(w) \pi_2(w)$} over alphabet {0,1}? Polynomial size in $|w|=n$
249 views

### Software/algorithm for the smallest context free grammar describing a set of words?

I am looking for software/algorithm for the smallest context free grammar describing a finite set of words (and no other words). For a single word I found sequitur Related to this seems: given a CFG ...
248 views

### Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}? One case this is possible is when ...
2k views

### What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
205 views

### Can a polynomial size CFG over large alphabet describe any of these languages:

Can a polynomial size CFG over large alphabet describe any of these languages: Each terminal appears 0 or 2 times Word repetition {www* | w \in \Sigma *} (word repetition of an arbitrary word w) ...