Tummel
unregistriert
 |
|
| Entscheidbar ob Sprachen einer Komplexitätsklasse angehören? |
     |
Meine Frage:
Welche der folgenden Sprachen sind entscheidbar, welche nicht? Begründen Sie Ihre Antworten. ¨
a) { G | G ist eine Grammatik und L(G) element P}
b) { G | G ist eine kontextfreie Grammatik und L(G) element NP}
( G kodiert/gödelisiert)
Meine Ideen:
Eine Verständnisfrage - bin dankbar für jeden Hinweis.
Vielleicht nein für a) ? Die Sprachfamilie der Komplexitätsklasse P ist eine Teilmenge der Sprachfamilie der Komplexitätsklasse NP, doch ist deren Verhältnis zueinander ja ungeklärt (P-NP-Problem).
|
|
17.01.2019 19:07 |
|
|
