Skip to main content
Computer Science

Return to Question

Clearer explanation.
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Undecidability of checking whether any wordall words can be generated from a context-free grammar?

I know it's undecidable, but how to prove it? Edit: It seems my description wasn't clear enough,

Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

Undecidability of checking whether any word can be generated from a context-free grammar?

I know it's undecidable, but how to prove it? Edit: It seems my description wasn't clear enough, the problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

Undecidability of checking whether all words can be generated from a context-free grammar?

I know it's undecidable, but how to prove it?

Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

added 182 characters in body
Source Link
InferionEmperor
InferionEmperor
  • 11
  • 3

I know it's undecidable, but how to prove it? Edit: It seems my description wasn't clear enough, the problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

I know it's undecidable, but how to prove it?

I know it's undecidable, but how to prove it? Edit: It seems my description wasn't clear enough, the problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

Source Link
InferionEmperor
InferionEmperor
  • 11
  • 3

Undecidability of checking whether any word can be generated from a context-free grammar?

I know it's undecidable, but how to prove it?