2
$\begingroup$

Prove that following problem is complete in NP in sense of Karp.

Given: context free grammar $G$

Check if $G$ generates word containing all symbols from alphabet

Remark Above problem should be encoded as langauge over finite alphabet, although alphabet of $G$ can be arbitrarily big. You can assume that symbols of this alphabet are encoded as binary strings.

My main problem at this moment is that I don't understand Remark. For me, it should be attached also alphabet of grammar. Can you explain me in human language what this Remark try to say ?
To be more clear I can say that in other task with the same question, but with given regex and alphabet of regex I did deal with it. However, in mentioned task there was no this awkward Remark.

|cite|improve this question
$\endgroup$
  • $\begingroup$ The title of your question doesn't match your question. Please modify your title accordingly, since all current answers refer to the body of your question. $\endgroup$ – Yuval Filmus Aug 12 '17 at 9:58
  • $\begingroup$ Consider it done! $\endgroup$ – Haskell Fun Aug 12 '17 at 10:37
1
$\begingroup$

The remark addresses the following problem:

How to encode context-free grammars over an arbitrary alphabet using a fixed alphabet?

Besides the alphabet, you encounter a similar problem when trying to represent non-terminals. The solution suggested by the remark is to use binary encoding. For example, the grammar

$$ S\to SA | \epsilon \\ A \to a | b | c $$

could be encoded as follows:

$$ N0; \to N0;N1; | \epsilon \\ N1; \to T0; | T1; | T10; $$

Another potential encoding is unary encoding:

$$ N0 \to N0N00|\epsilon \\ N1 \to T0|T00|T000 $$

Which encoding is used can affect the complexity of the problem. For example, problems like Knapsack and Subset-Sum are NP-hard for binary encoding, but become easy when unary encoding is used (such problems are known as weakly polynomial).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Obviously given grammar is over finite alphabet but we can't know size its. Remark make us to explain how we encode problem, e.g. how we encode symbols from grammar's alphabet and terminals. The suggestion is about representing symbols from alphabet by binary strings (more exactly symbols are enumarated from 0 to ... and represent in binary system). When it comes to terminals you propose nice way of encoding, $Nk$ where $k$ is number of non-terminal (we also enumerate them). Can I properly understand you ? $\endgroup$ – Haskell Fun Aug 12 '17 at 10:56
  • 1
    $\begingroup$ Yes, this is what I meant. $\endgroup$ – Yuval Filmus Aug 12 '17 at 12:02
2
$\begingroup$

What the remark is trying to tell you, I think, is that the alphabet of each different grammar $G$ can grow and is not fixed.

For instance. say that you have a language $L$ that you want to reduce to your language, let´s call it $L'$, then, you are allowed to make the alphabet of the different context free grammars inside $L'$ grow as the instances inside $L$ grow. For a bigger instance a bigger alphabet

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.