Jak mogę udowodnić, że konwersja z CNF do DNF jest NP-trudna? Nie proszę o odpowiedź, tylko kilka sugestii na temat tego, jak to
Kolejność aplikacji: Zawsze w pełni oceniaj argumenty funkcji przed oceną samej funkcji, na przykład - (λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x....
Rozumiem, że gramatyki bezkontekstowe mogą być używane do reprezentowania języków bezkontekstowych. Mogą być niejasne. Mamy również normalne formy, takie jak normalna postać Chomsky'ego i Greibacha . Nie mogłem zrozumieć takiej potrzeby. Dlaczego są ważne w teorii języków? Wszystkie podręczniki, o...
W odniesieniu do wątku Udowodnienie, że konwersja z CNF do DNF jest NP-twarda (i powiązany wątek matematyczny ): Co powiesz na inny kierunek, od DNF do CNF? Czy to jest łatwe czy trudne? Na stronie 2 tego artykułu wydają się sugerować, że oba kierunki są równie trudne, gdy mówią: „ Jesteśmy...