मैं अभ्यास कार्य में संदर्भ मुक्त व्याकरण के आवेदन को औपचारिक बनाने की कोशिश कर रहा हूं। मुझे एक प्रमेयिका सिद्ध करने में समस्या होती है। मैंने समस्या को रेखांकित करने के लिए अपने संदर्भ को सरल बनाने की कोशिश की, लेकिन यह अभी भी थोड़ा बोझिल है।

इसलिए मैंने सीएफजी को चॉम्स्की सामान्य रूप में परिभाषित किया और टर्मिनलों की सूची की व्युत्पत्ति इस प्रकार है:

Require Import List.
Import ListNotations.

Inductive ter : Type := T : nat -> ter.
Inductive var : Type := V : nat -> var.
Inductive eps : Type := E : eps.

Inductive rule : Type :=
  | Rt : var -> ter -> rule
  | Rv : var -> var -> var -> rule
  | Re : var -> eps -> rule.

Definition grammar := list rule.

Inductive der_ter_list : grammar -> var -> list ter -> Prop :=
  | Der_eps : forall (g : grammar) (v : var) (e : eps),
      In (Re v e) g -> der_ter_list g v []
  | Der_ter : forall (g : grammar) (v : var) (t : ter),
      In (Rt v t) g -> der_ter_list g v [t]
  | Der_var : forall (g : grammar) (v v1 v2 : var) (tl1 tl2 : list ter),
      In (Rv v v1 v2) g -> der_ter_list g v1 tl1 -> der_ter_list g v2 tl2 ->
        der_ter_list g v (tl1 ++ tl2).

मेरे पास ऐसी वस्तुएं हैं जो टर्मिनल और कुछ अतिरिक्त जानकारी संग्रहीत करती हैं, उदाहरण के लिए:

Inductive obj : Set := Get_obj : nat -> ter -> obj.

और मैं वस्तुओं की सभी संभावित सूचियों को परिभाषित करने का प्रयास करता हूं, जो दिए गए गैर-टर्मिनल (सहायक कार्यों के साथ) से व्युत्पन्न हैं:

Fixpoint get_all_pairs (l1 l2 : list (list obj)) : list (list obj) := match l1 with
    | [] => []
    | l::t => (map (fun x => l ++ x) l2) ++ get_all_pairs t l2
  end.

Fixpoint getLabels (objs : list obj) : list ter := match objs with
    | [] => []
    | (Get_obj yy ter)::t => ter::(getLabels t)
  end.

Inductive paths : grammar -> var -> list (list obj) -> Prop :=
  | Empty_paths : forall (g : grammar) (v : var) (e : eps),
      In (Re v e) g -> paths g v [[]]
  | One_obj_path : forall (g : grammar) (v : var) (n : nat) (t : ter) (objs : list obj),
      In (Rt v t) g -> In (Get_obj n t) objs -> paths g v [[Get_obj n t]]
  | Combine_paths : forall (g : grammar) (v v1 v2 : var) (l1 l2 : list (list obj)),
      In (Rv v v1 v2) g -> paths g v1 l1 -> paths g v2 l2 -> paths g v (get_all_pairs l1 l2).

(paths का प्रत्येक कंस्ट्रक्टर वास्तव में rule के कंस्ट्रक्टर से मेल खाता है)

और अब मैं प्रेरण द्वारा paths के बारे में तथ्य को प्रमाणित करने का प्रयास कर रहा हूं, कि paths में प्रत्येक तत्व गैर-टर्मिनल से प्राप्त किया जा सकता है:

Theorem derives_all_path : forall (g: grammar) (v : var)
  (ll : list (list obj)) (pths : paths g v ll), forall (l : list obj),
        In l ll -> der_ter_list g v (getLabels l).
Proof.
  intros g v ll pt l contains.
  induction pt.

यह निर्माण 3 उप-लक्ष्य उत्पन्न करता है, पहला और दूसरा मैंने क्रमशः Der_eps और Der_ter कंस्ट्रक्टरों को लागू करके साबित किया है। लेकिन मेरे लक्ष्य को साबित करने के लिए तीसरे उप-लक्ष्य का संदर्भ प्रासंगिक नहीं है, इसमें यह है:

contains : In l (get_all_pairs l1 l2)
IHpt1 : In l l1 -> der_ter_list g v1 (getLabels l)
IHpt2 : In l l2 -> der_ter_list g v2 (getLabels l)

तो contains का मतलब है कि l, l1 और l2 से कुछ तत्वों का संयोजन है, लेकिन IHpt1 और IHpt2 में परिसर सही हैं अगर l2 और l1 में खाली सूचियां हैं, जो सामान्य रूप से सत्य नहीं है, इसलिए इस संदर्भ में लक्ष्य को सिद्ध करना असंभव है।

समस्या का समाधान किया जा सकता है यदि l में contains, IHpt1, IHpt2 अलग-अलग सूचियां होंगी, लेकिन दुर्भाग्य से मुझे नहीं पता कि इसे Coq को कैसे समझाऊं। क्या यह किसी भी तरह से लक्ष्य को साबित करने के लिए IHpt1 और IHpt2 को बदलना है, या किसी अन्य तरीके से पूरे तथ्य को साबित करना है?

मैंने paths_ind को देखने की कोशिश की, लेकिन इससे मुझे खुशी नहीं हुई।

3
Roman Fedorov 16 मई 2017, 22:58
स्टैक ओवरफ्लो में आपका स्वागत है!
 – 
Anton Trunov
16 मई 2017, 23:33

1 उत्तर

सबसे बढ़िया उत्तर

ऐसा लगता है कि आपकी प्रेरण परिकल्पना पर्याप्त मजबूत नहीं है। यदि आप अधिक बहुरूपी लक्ष्य पर induction pt प्रदर्शन करते हैं, तो आपको अधिक उपयोगी परिकल्पनाएं मिलेंगी जो उस विशिष्ट l से जुड़ी नहीं हैं, जिसके साथ आपने शुरुआत की थी।

तुम्हें कोशिश करनी चाहिए:

intros g v ll pt; induction pt; intros l contains.
2
gallais 16 मई 2017, 23:40