{"assessment":{"class":"B","importance":"high"},"audit":{"blind":true,"ended":"2026-11-03T02:10:43.537Z","figures":[{"ci95":[0.4891,0.9935],"drawn":36,"id":"primary","label":"Strong links (exact, close or broad match) on supporting passages that have exactly the right relation","n_eff":5.1,"population":1029,"share":0.9234,"weights":"relation and library"},{"ci95":[0.3979,0.9202],"drawn":48,"id":"S2","label":"Links in a counting relation (exact, close, broad, narrow match or part) on supporting passages that have exactly the right relation","n_eff":8.1,"population":1740,"share":0.734,"weights":"relation and library"},{"ci95":[0.7268,0.9357],"drawn":44,"id":"CS","label":"Central and subject passages whose formalization status is right","n_eff":42.0,"population":1905,"share":0.8615,"weights":"recorded status"},{"ci95":[0.2519,0.8658],"drawn":12,"id":"S3","label":"'Not formalized' on supporting passages that is right (no declaration in the 48 libraries states it)","n_eff":6.1,"population":1236,"share":0.5957,"weights":"article"}],"independent":false,"items":224,"models":[{"model":"claude-opus-5-5","model_name":"Claude Opus 5.5"}],"operator":"jack","run_id":"tierA-batch1-audit","started":"2026-11-02T21:10:01.351Z"},"campaign":"run:loc-tierA-b1b+chal-tierA-b1","licence":{"mapping":"CC0-1.0","text":"CC-BY-SA-4.0"},"pageid":653406,"passages":[{"absence":null,"basis":"b40e59066bdfae2ccb4c0e3067519a7c844f3e81c366445092edf08ebaf71d5f","coverage":null,"id":"enwiki-653406-1366106761::In-text #2a28a06c","item":"In-text #2a28a06c","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA","end_line":65,"library":"mathlib","line":59,"location_key":"b40e59066bdfae2ccb4c0e3067519a7c844f3e81c366445092edf08ebaf71d5f","module":"Mathlib.Computability.DFA","note":"Mathlib bundles a state type, a transition taking a state and a symbol to a single state, one start state and a set of accepting states; because the transition is a total function into the state type, determinism and symbol-consuming steps both hold by construction, while the state type may be any type.","pair_key":"bfcc9380737c5b06fc7868529f28abed5dfa40b8f9828c27c4a68b18fe63eb92","path":"Mathlib/Computability/DFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"structure DFA : Type u → Type v → Type (max u v)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"01b4a7119639dd042b8c0101acba5c9f06da93ad4cb4cf7d8f7e16b1f2e89aea","prominence":"central","quote":{"exact":"each of its transitions is uniquely determined by its source state and"},"quote_capped":true,"section":[],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if ","lead_in":true,"segments":[{"text":"In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if "}]},"layer":"each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition.","segments":[{"text":"each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition."}]},"unresolved":null},{"absence":null,"basis":"07ee59030fac54a127f951467b9ecb3cdbfef232b1f49583ad8dccb53e45732d","coverage":null,"id":"enwiki-653406-1366106761::In-text #7c3d2169","item":"In-text #7c3d2169","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA","end_line":48,"library":"mathlib","line":40,"location_key":"07ee59030fac54a127f951467b9ecb3cdbfef232b1f49583ad8dccb53e45732d","module":"Mathlib.Computability.EpsilonNFA","note":"The structure's docstring says the state type may be infinite and that a step labelled by the empty option reads no symbol; those are exactly the two freedoms the article grants over a deterministic machine.","pair_key":"1d4d8485537f2618d9bebd7dd862aa74dcd08138924ec75c39b0d6c425a019c7","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"structure εNFA : Type u → Type v → Type (max u v)"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA","end_line":61,"library":"mathlib","line":55,"location_key":"4844354565b1d9f51340b90b4a5dabee544c65eae7c6aec5abfb9b79d840efee","module":"Mathlib.Computability.NFA","note":"Mathlib keeps symbol-free steps in a separate structure, so this one covers the article's machines whose every transition consumes a symbol, with the state type unconstrained.","pair_key":"c0763476f9375e8959ee0e89c2b17da965d6e8e5ba4fe5c8b60e273e7254d708","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"narrowMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"structure NFA : Type u → Type v → Type (max u v)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"944ba1cf10ee4859d356cb9c574f28b7b2e33979cbfc3381cac675af62bdc386","prominence":"subject","quote":{"exact":"A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need"},"quote_capped":true,"section":[],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions.","segments":[{"text":"A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions."}]},"unresolved":null},{"absence":null,"basis":"231389233d4ff53f567e39e29d97f5cbc175a84296156b3f2ede2c0f39f25e73","coverage":null,"id":"enwiki-653406-1366106761::In-text #143b801f","item":"In-text #143b801f","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA_correct","end_line":354,"library":"mathlib","line":348,"location_key":"231389233d4ff53f567e39e29d97f5cbc175a84296156b3f2ede2c0f39f25e73","module":"Mathlib.Computability.NFA","note":"Mathlib keeps the two kinds of machine as separate structures and writes the inclusion as a construction that keeps the start and accepting states and makes each step a one-element set, together with this equality of accepted languages; the state type is arbitrary.","pair_key":"15a7f93bcf04ca245c7481f41028f716571d034ae7255c15db16de26e8d06d7a","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA","end_line":334,"library":"mathlib","line":331,"location_key":"005819f35953b8ab0bf2db630882752409d1fdb9c2eb23828dfb2cc25faf4508","module":"Mathlib.Computability.NFA","note":"The construction that reads a deterministic machine as a nondeterministic one, with singleton step sets; by itself it carries no claim about the words accepted.","pair_key":"060e1d82514af549c185b597338afa8d28182cf35f381bc548558600e9841921","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def DFA.toNFA {α : Type u} {σ : Type v} : DFA α σ → NFA α σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"f0ce3c925799dd6f0599e7f87bafe078668a08ee8e6c8d8f0207c891e1bf5899","prominence":"central","quote":{"exact":"In particular, every DFA is also an NFA."},"quote_capped":false,"section":[],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"In particular, every DFA is also an NFA.","segments":[{"text":"In particular, every DFA is also an NFA."}]},"unresolved":null},{"absence":null,"basis":"558f17435434ab9b9b61adfc81387df3725de5de5768982844eeb58fb4cb9ddb","coverage":null,"id":"enwiki-653406-1366106761::In-text #cb6cd51a","item":"In-text #cb6cd51a","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA_correct","end_line":315,"library":"mathlib","line":312,"location_key":"558f17435434ab9b9b61adfc81387df3725de5de5768982844eeb58fb4cb9ddb","module":"Mathlib.Computability.NFA","note":"The deterministic machine here is the one whose states are sets of the original states, built by the construction the article names, and the theorem equates the two accepted languages for every state type.","pair_key":"4c316308015dc8bf08873e188291482e4f1357ef1a9ab1a90d92fd7cbd65e0a4","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA","end_line":309,"library":"mathlib","line":306,"location_key":"2c0f9d0e182701d3844061fb35fa813ae5e2fb12b34b14436010e9b06db691b6","module":"Mathlib.Computability.NFA","note":"The construction itself, whose states are sets of the original states and whose step is the one-symbol image of a set of states; on its own it says nothing about accepted words.","pair_key":"9077c33c483d4de51d48ec85e3ac117e721d17216f3d988d85a020e6dde55413","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"89722902a65d851ddc8e00c6b0dd0f44004b19763af48509a386217c05d74578","prominence":"central","quote":{"exact":"Using the subset construction algorithm, each NFA can be translated to an"},"quote_capped":true,"section":[],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language.[1]","segments":[{"text":"Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language."},{"ref":"[1]"}]},"unresolved":null},{"absence":null,"basis":"2522f4a452d5448d21087bbfa676531449acff7c9351bd571a812188598d0aaa","coverage":null,"id":"enwiki-653406-1366106761::In-text #a32da92c","item":"In-text #a32da92c","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"Language.isRegular_iff","end_line":374,"library":"mathlib","line":372,"location_key":"2522f4a452d5448d21087bbfa676531449acff7c9351bd571a812188598d0aaa","module":"Mathlib.Computability.DFA","note":"Mathlib fixes regularity by the existence of a finite deterministic machine, so this equivalence delivers the article's conclusion exactly for the deterministic automata among its machines; the nondeterministic ones are not reached by it alone.","pair_key":"9e7ef2bd906b41cae451b4b20d13f92c253b3c5c40599a566b514f790f8f2481","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":1,"relation":"narrowMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem Language.isRegular_iff {T : Type u} {L : Language T} : L.IsRegular ↔ ∃ σ x M, M.accepts = L"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA_correct","end_line":315,"library":"mathlib","line":312,"location_key":"c518b1eb0919a72f8f82ebbbb4e4083b3562de39af4a753be1b88866efb5986d","module":"Mathlib.Computability.NFA","note":"It equates the language of a nondeterministic machine with that of its determinisation; reaching regularity needs in addition that sets over a finite state set form a finite type and Mathlib's characterisation of regular languages.","pair_key":"63e30b6a7a7e7cc29b961798d8369d3106e658a85c61a8131673c2342db76e14","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"497a7e4f7fed896690c90c26fd30d9fd95ef3a26bf765dd86183c06b818035dd","prominence":"central","quote":{"exact":"Like DFAs, NFAs only recognize regular languages."},"quote_capped":false,"section":[],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Like DFAs, NFAs only recognize regular languages.","segments":[{"text":"Like DFAs, NFAs only recognize regular languages."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":4,"queries":4,"sha256":"8dd58405e51cfb9919456ca2a8b2d7e289eb447fdf67d6093551673b433d2315"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #d37a78fd","item":"In-text #d37a78fd","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"10aeacdb66ee5f43b7f7913794677ab6fa2bb1c7bf4733cc4659965103e11027","prominence":"supporting","quote":{"exact":"Conversely, Kleene's algorithm can be used to convert an NFA into a"},"quote_capped":true,"section":[],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton).","segments":[{"text":"Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton)."}]},"unresolved":null},{"absence":null,"basis":"e186a1d48bce9e61e08a860d40f0508e7d95f9a0dea4c5c68933e69b2df7a246","coverage":null,"id":"enwiki-653406-1366106761::In-text #1f803bcb","item":"In-text #1f803bcb","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts_iff_exists_path","end_line":301,"library":"mathlib","line":298,"location_key":"552c52534a46b8edaaec38014fb9167eee2709fc234ba3738ff464a7e4ff2d87","module":"Mathlib.Computability.NFA","note":"A run in Mathlib is an inductive path labelled by the word, so a path from a start state to an accepting state is one sequence of applicable transitions that consumes the whole word; the state type is left arbitrary.","pair_key":"f9ba6cbb2d43758ff9ec9bcb4f14947ea1f4b3eb0cd8a292c428b197b01c168d","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts","end_line":253,"library":"mathlib","line":253,"location_key":"e186a1d48bce9e61e08a860d40f0508e7d95f9a0dea4c5c68933e69b2df7a246","module":"Mathlib.Computability.NFA","note":"This is the object the article's sentence defines: the language of words leading the machine, under some choice of transitions, into an accepting state; Mathlib states it for any state type.","pair_key":"a1c8a7b5ac08b1072ea957590d532246927342c49added77b5e8513328eaa01f","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"b98158ba995c23cde3ea4b40a9140336a52f4b7ec66f0fd2173992a102680827","prominence":"central","quote":{"exact":"If there exists at least one \"lucky run\", i.e. some sequence of"},"quote_capped":true,"section":["Informal introduction"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"If there exists at least one \"lucky run\", i.e. some sequence of choices leading to an accepting state after completely consuming the input, it is accepted.","segments":[{"text":"If there exists at least one \"lucky run\", i.e. some sequence of choices leading to an accepting state after completely consuming the input, it is accepted."}]},"unresolved":null},{"absence":null,"basis":"80a4bf35d156fb6fc96fd1fd36b5b7c1ff55967b97120270d6fab4d4e59ee840","coverage":null,"id":"enwiki-653406-1366106761::In-text #13ed5544","item":"In-text #13ed5544","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.accepts_iff_exists_path","end_line":301,"library":"mathlib","line":298,"location_key":"80a4bf35d156fb6fc96fd1fd36b5b7c1ff55967b97120270d6fab4d4e59ee840","module":"Mathlib.Computability.NFA","note":"Mathlib has no separate name for a refused input: it is simply a word outside the accepted language, and this equivalence read negatively is the article's condition that no choice sequence works.","pair_key":"b48003ed3f05db3d549737a7c142020a89a351afac0881aac60e002809dc9c7a","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"ca639a37f435629adadc03f82df0a79412ea6bbe3e99da88e230dde2fc1287a6","module":"Mathlib.Computability.NFA","note":"The same criterion through step-by-step evaluation: the set of states reachable after the whole word meets the accepting states, whose failure is the article's refusal of the input.","pair_key":"f8589b1552074900bf7fc1f89cd5c23e4ecbc879df6ca997787e51acd13bd456","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"88b212e34af7a4ac477a155df426b6f5aa31cf347937b7470f836a90f024eb8b","prominence":"supporting","quote":{"exact":"Otherwise, i.e. if no choice sequence at all can consume all the"},"quote_capped":true,"section":["Informal introduction"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Otherwise, i.e. if no choice sequence at all can consume all the input[3] and lead to an accepting state, the input is rejected.","segments":[{"text":"Otherwise, i.e. if no choice sequence at all can consume all the input"},{"ref":"[3]"},{"text":" and lead to an accepting state, the input is rejected."}]},"unresolved":null},{"absence":null,"basis":"feec548378f023b27d7463d1a3b4c18568e340459c4dd165d2e54d60bc2c1e39","coverage":null,"id":"enwiki-653406-1366106761::In-text #f9692420","item":"In-text #f9692420","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"11c97cb253d43d62c7bb130cef31a3aba2e4a0a347161390c79e848b95a6be36","module":"Mathlib.Computability.NFA","note":"Mathlib's set of states reached after the input is the collection of copies still alive in the cloning picture, and the lemma is stated for machines with a whole set of start states.","pair_key":"247d36f6476f06be31e14fca357bf3d70ebfb9affa9ff820ad57cd6d19e0c4e7","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.accepts","end_line":253,"library":"mathlib","line":253,"location_key":"feec548378f023b27d7463d1a3b4c18568e340459c4dd165d2e54d60bc2c1e39","module":"Mathlib.Computability.NFA","note":"This is the defined object: the language whose members are the inputs with an accepting state among those reached, over arbitrary state and letter types.","pair_key":"072524b8d139443752b665feb287ba73fe9b06773826e4aa79892937c540f940","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"8509b69200e474cf5634e03d4f33cb7760d987afada3b123d4e4b201133413ad","prominence":"supporting","quote":{"exact":"If, after consuming the complete input, any of the copies is in"},"quote_capped":true,"section":["Informal introduction"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected.","segments":[{"text":"If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected."}]},"unresolved":null},{"absence":null,"basis":"ca57f84f93962ae627bef442ac29b4dfcfa52fcf85b0e579d3a51d83539bea17","coverage":null,"id":"enwiki-653406-1366106761::In-text #a34ed415","item":"In-text #a34ed415","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA","end_line":61,"library":"mathlib","line":55,"location_key":"ca57f84f93962ae627bef442ac29b4dfcfa52fcf85b0e579d3a51d83539bea17","module":"Mathlib.Computability.NFA","note":"Mathlib leaves the state and letter types unrestricted where the article asks for finite ones, and carries a whole set of start states where the article distinguishes one element, so it is inhabited by more machines than the article defines.","pair_key":"5b276120706bcff4956031e2f506365bee13e7b9e373a42662b06bc57d3c41ff","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"structure NFA : Type u → Type v → Type (max u v)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"9b624c6ce3141c437e7d4a156b9b0c55672af6a0c4ff6436a14fdbeeb6c0f55b","prominence":"central","quote":{"exact":"a finite set of states Q {\\displaystyle Q} , a finite set"},"quote_capped":true,"section":["Formal definition","Automaton"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"An NFA is represented formally by a 5-tuple, ( Q , Σ , δ , q 0 , F ) {\\displaystyle (Q,\\Sigma ,\\delta ,q_{0},F)} , consisting of ","lead_in":true,"segments":[{"text":"An NFA is represented formally by a 5-tuple, "},{"tex":"(Q,\\Sigma ,\\delta ,q_{0},F)"},{"text":" , consisting of "}]},"layer":"a finite set of states Q {\\displaystyle Q} , a finite set of input symbols called the alphabet Σ {\\displaystyle \\Sigma } , a transition function δ {\\displaystyle \\delta } : Q × Σ → P ( Q ) {\\displaystyle Q\\times \\Sigma \\rightarrow {\\mathcal {P}}(Q)} , an initial (or start) state q 0 ∈ Q {\\displaystyle q_{0}\\in Q} , and a set of accepting (or final) states F ⊆ Q {\\displaystyle F\\subseteq Q} .","segments":[{"text":"a finite set of states "},{"tex":"Q"},{"text":" , a finite set of input symbols called the alphabet "},{"tex":"\\Sigma"},{"text":" , a transition function "},{"tex":"\\delta"},{"text":" : "},{"tex":"Q\\times \\Sigma \\rightarrow {\\mathcal {P}}(Q)"},{"text":" , an initial (or start) state "},{"tex":"q_{0}\\in Q"},{"text":" , and a set of accepting (or final) states "},{"tex":"F\\subseteq Q"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"76c145a017aaf25b47f484a643b3f2d41c00b169a9096a52cb41b2442fd6d007","coverage":null,"id":"enwiki-653406-1366106761::In-text #dcec0d00","item":"In-text #dcec0d00","kind":"notation","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"Finset.powerset","end_line":33,"library":"mathlib","line":31,"location_key":"76c145a017aaf25b47f484a643b3f2d41c00b169a9096a52cb41b2442fd6d007","module":"Mathlib.Data.Finset.Powerset","note":"Mathlib carries the finite state set and each of its subsets as finite-set terms rather than as sets of states.","pair_key":"2acf650a636b1ee6e8321eb1f852c547268d261f8599f50b82f98f930aed4324","path":"Mathlib/Data/Finset/Powerset.lean","proof_status":"definition","rank":1,"relation":"closeMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def Finset.powerset {α : Type*} : Finset α → Finset (Finset α)"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"Set.powerset","end_line":255,"library":"mathlib","line":255,"location_key":"072c3735dabca3d2bf4f8f2a06481b7f038476eb1ac0040b6c78543e6e497e78","module":"Mathlib.Data.Set.Defs","note":"Mathlib gives the power set of an arbitrary set, including infinite ones, where the passage names it for the finite state set of an automaton.","pair_key":"95ae98f3860b45c199e637bd7600d6c1861a1cbf099492225ac46371d1cf3bfe","path":"Mathlib/Data/Set/Defs.lean","proof_status":"definition","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def Set.powerset {α : Type u} : Set α → Set (Set α)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":true,"passage_key":"78fb798d00a6934b8a69ec41caf5c8dd6b8527bac857f47b197d03f68f5b6059","prominence":"supporting","quote":{"exact":"Here, P ( Q ) {\\displaystyle {\\mathcal {P}}(Q)} denotes the power set","suffix":" of Q {\\displaystyle Q} ."},"quote_capped":true,"section":["Formal definition","Automaton"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Here, P ( Q ) {\\displaystyle {\\mathcal {P}}(Q)} denotes the power set of Q {\\displaystyle Q} .","segments":[{"text":"Here, "},{"tex":"{\\mathcal {P}}(Q)"},{"text":" denotes the power set of "},{"tex":"Q"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"3b3d8305b26397d0ac35d0172072e5695151771fab31acaecad9aa35a6858030","coverage":null,"id":"enwiki-653406-1366106761::In-text #4c2b539a","item":"In-text #4c2b539a","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts","end_line":253,"library":"mathlib","line":253,"location_key":"3b3d8305b26397d0ac35d0172072e5695151771fab31acaecad9aa35a6858030","module":"Mathlib.Computability.NFA","note":"Mathlib returns the accepted language of a machine whose carriers may be infinite and whose start states form a set, where the passage fixes a finite machine with one start state.","pair_key":"70b627f9578da1eb72c7f95f0235378cec10d8c43a21e77770d127319fd9abde","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"b6306515ba7e84db334c6fa677a60cbe5d35711cc12fc03ecdd9d1adccfa3b37","prominence":"central","quote":{"exact":"Given an NFA M = ( Q , Σ , δ ,"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Given an NFA M = ( Q , Σ , δ , q 0 , F ) {\\displaystyle M=(Q,\\Sigma ,\\delta ,q_{0},F)} , its recognized language is denoted by L ( M ) {\\displaystyle L(M)} , and is defined as the set of all strings over the alphabet Σ {\\displaystyle \\Sigma } that are accepted by M {\\displaystyle M} .","segments":[{"text":"Given an NFA "},{"tex":"M=(Q,\\Sigma ,\\delta ,q_{0},F)"},{"text":" , its recognized language is denoted by "},{"tex":"L(M)"},{"text":" , and is defined as the set of all strings over the alphabet "},{"tex":"\\Sigma"},{"text":" that are accepted by "},{"tex":"M"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"55fe71a5108b44e862a10b6ae3e0368f5e962de42fdcb7f96bafb333a3688f1f","coverage":null,"id":"enwiki-653406-1366106761::In-text #36ff5432","item":"In-text #36ff5432","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts_iff_exists_path","end_line":301,"library":"mathlib","line":298,"location_key":"55fe71a5108b44e862a10b6ae3e0368f5e962de42fdcb7f96bafb333a3688f1f","module":"Mathlib.Computability.NFA","note":"Mathlib packages the run as an inductive family of paths rather than as an indexed list of states, and allows several start states where the passage has one.","pair_key":"ad672c44db1a19cf2f51693677524bafa6d42f6eeca13c1c4dd57e990de05e8e","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.Path","end_line":272,"library":"mathlib","line":269,"location_key":"2e34161e56abad3d805a07d8eb1b04d01826a56cd48483bc5e461797b48416aa","module":"Mathlib.Computability.NFA","note":"Mathlib carries the run as data indexed by its endpoints and its word, rather than as a list of states indexed by position.","pair_key":"14d64ca91fba29ecf968e4f34704aae4c4e75910c6966608bd792670c7fddc2e","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"inductive NFA.Path {α : Type u} {σ : Type v} : NFA α σ → σ → σ → List α → Type (max u v)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"b0c35db2daaef568fc52ee43d0eacba31551e0fc6a0ec9b66cc37b2773858f2f","prominence":"central","quote":{"exact":"w {\\displaystyle w} is accepted if a sequence of states, r 0"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string w = a 1 a 2 . . . a n {\\displaystyle w=a_{1}a_{2}...a_{n}} being accepted by M {\\displaystyle M} : ","lead_in":true,"segments":[{"text":"Loosely corresponding to the above informal explanations, there are several equivalent formal definitions of a string "},{"tex":"w=a_{1}a_{2}...a_{n}"},{"text":" being accepted by "},{"tex":"M"},{"text":" : "}]},"layer":"w {\\displaystyle w} is accepted if a sequence of states, r 0 , r 1 , . . . , r n {\\displaystyle r_{0},r_{1},...,r_{n}} , exists in Q {\\displaystyle Q} such that: r 0 = q 0 {\\displaystyle r_{0}=q_{0}} r i + 1 ∈ δ ( r i , a i + 1 ) {\\displaystyle r_{i+1}\\in \\delta (r_{i},a_{i+1})} , for i = 0 , … , n − 1 {\\displaystyle i=0,\\ldots ,n-1} r n ∈ F {\\displaystyle r_{n}\\in F} .","segments":[{"tex":"w"},{"text":" is accepted if a sequence of states, "},{"tex":"r_{0},r_{1},...,r_{n}"},{"text":" , exists in "},{"tex":"Q"},{"text":" such that: "},{"tex":"r_{0}=q_{0}"},{"text":" "},{"tex":"r_{i+1}\\in \\delta (r_{i},a_{i+1})"},{"text":" , for "},{"tex":"i=0,\\ldots ,n-1"},{"text":" "},{"tex":"r_{n}\\in F"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"b736c8118a7902e8370624754d008b86aca704365004a7c643d000998cc7aebd","coverage":null,"id":"enwiki-653406-1366106761::In-text #29e0d6d1","item":"In-text #29e0d6d1","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts_iff_exists_path","end_line":301,"library":"mathlib","line":298,"location_key":"b736c8118a7902e8370624754d008b86aca704365004a7c643d000998cc7aebd","module":"Mathlib.Computability.NFA","note":"Mathlib proves the full equivalence, whose right-to-left half is the sufficiency the passage asserts, and it holds for machines with a set of start states.","pair_key":"b31acd2aa929762cf4aa993e797745787f843b751ed1bf2e7293e8218e76653a","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"db27cfc0475cb22cb01e9df81cc1d5d0ddf41954410433ae6d83a992521dd2ff","prominence":"supporting","quote":{"exact":"In order for w {\\displaystyle w} to be accepted by M {\\displaystyle"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"In order for w {\\displaystyle w} to be accepted by M {\\displaystyle M} , it is not required that every state sequence ends in an accepting state, it is sufficient if one does.","segments":[{"text":"In order for "},{"tex":"w"},{"text":" to be accepted by "},{"tex":"M"},{"text":" , it is not required that every state sequence ends in an accepting state, it is sufficient if one does."}]},"unresolved":null},{"absence":null,"basis":"91835f79dc6587d248c4f78909b42c577d08adfe22687fad863d5ac9afcc3cb8","coverage":null,"id":"enwiki-653406-1366106761::In-text #fb8d0f52","item":"In-text #fb8d0f52","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.accepts_iff_exists_path","end_line":301,"library":"mathlib","line":298,"location_key":"91835f79dc6587d248c4f78909b42c577d08adfe22687fad863d5ac9afcc3cb8","module":"Mathlib.Computability.NFA","note":"Mathlib has no separate predicate for rejection: a rejected word is one outside the machine's accepted language, and the lemma is stated for machines with a set of start states.","pair_key":"25c991217ad4c8c662d2b073c810a531b6d3f1971173044dba37eda512c5e553","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"a0740181ecb6018f0773291940c0136b91e624ec04953e7a306900f75e374f7a","prominence":"supporting","quote":{"exact":"Otherwise, i.e. if it is impossible at all to get from q"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Otherwise, i.e. if it is impossible at all to get from q 0 {\\displaystyle q_{0}} to a state from F {\\displaystyle F} by following w {\\displaystyle w} , it is said that the automaton rejects the string.","segments":[{"text":"Otherwise, i.e. if it is impossible at all to get from "},{"tex":"q_{0}"},{"text":" to a state from "},{"tex":"F"},{"text":" by following "},{"tex":"w"},{"text":" , it is said that the automaton rejects the string."}]},"unresolved":null},{"absence":null,"basis":"12cf053d91c0dce035bbb72a26da5af5ad3e79554c97f22df6bfc78a2714dbe1","coverage":null,"id":"enwiki-653406-1366106761::In-text #d439e09e","item":"In-text #d439e09e","kind":"definition","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts","end_line":253,"library":"mathlib","line":253,"location_key":"12cf053d91c0dce035bbb72a26da5af5ad3e79554c97f22df6bfc78a2714dbe1","module":"Mathlib.Computability.NFA","note":"Mathlib names this language of a machine whose carriers may be infinite and whose start states form a set, where the passage has a finite machine with one start state.","pair_key":"15c46a08bf4736ceac9bdd2daf1cbea56521af741e37a9f4f01b5bb64956d3ad","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"6d205282d4f15987e8eb3390e30ba71b5bba6eda8b98c9f570ff7acf42f8afc7","prominence":"supporting","quote":{"exact":"The set of strings M {\\displaystyle M} accepts is the language recognized"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The set of strings M {\\displaystyle M} accepts is the language recognized by M {\\displaystyle M} and this language is denoted by L ( M ) {\\displaystyle L(M)} .","segments":[{"text":"The set of strings "},{"tex":"M"},{"text":" accepts is the language recognized by "},{"tex":"M"},{"text":" and this language is denoted by "},{"tex":"L(M)"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":null,"coverage":{"basis":true,"bundle_key":"1bb2e45bbabb993fe3f98beb7260567ca2e0ad1a4bf2e7a8cea1ed82ab1fe5a4","challenge":"survived","complete":true,"conjuncts":[{"id":"c1","part":"02b1a53a520f0b000de428b9e50eb941ff64200ec63bae865954073dc953669d","text":"w is accepted exactly when the set of states reached from the start state on w has a member in F"},{"id":"c2","part":"254a8a3b5368cb893c7885a5d84384a5578c84026381283608ccbb41131a610c","text":"on the empty string the extended transition function returns just the state itself"},{"id":"c3","part":"0653cc1deef2a0d01fddbd37ea5949cc8294f1d622055301234e5b85cde3b422","text":"on a string followed by a symbol it returns the union of the transition sets of that symbol over all states reached on the string"}],"parts":["02b1a53a520f0b000de428b9e50eb941ff64200ec63bae865954073dc953669d","254a8a3b5368cb893c7885a5d84384a5578c84026381283608ccbb41131a610c","0653cc1deef2a0d01fddbd37ea5949cc8294f1d622055301234e5b85cde3b422"],"relation":"broadMatch","status":"formalized"},"id":"enwiki-653406-1366106761::In-text #444362ab","item":"In-text #444362ab","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"02b1a53a520f0b000de428b9e50eb941ff64200ec63bae865954073dc953669d","module":"Mathlib.Computability.NFA","note":"Mathlib carries a set of start states and imposes no finiteness on states or symbols, so the singleton {q0} and the article's finite data are an instance of it.","pair_key":"ca9b72f221a02affc718c8c0511f1d12a63a9a8bede3271748719a6a7e731153","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.evalFrom_nil","end_line":103,"library":"mathlib","line":102,"location_key":"254a8a3b5368cb893c7885a5d84384a5578c84026381283608ccbb41131a610c","module":"Mathlib.Computability.NFA","note":"The equation is stated for an arbitrary set of states, and the one-element set {r} is the case the article writes.","pair_key":"3310943c71067f5aed8c3214dcd5c211a77f12687d612a2ffacaf58cd2cc935d","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.evalFrom_nil {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) : M.evalFrom S [] = S"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.evalFrom_append","end_line":120,"library":"mathlib","line":118,"location_key":"0653cc1deef2a0d01fddbd37ea5949cc8294f1d622055301234e5b85cde3b422","module":"Mathlib.Computability.NFA","note":"Evaluation on a one-symbol word is by definition Mathlib's step-set operation, namely the union of the transition sets over the current states.","pair_key":"484fca6f80bc1fc8ead6a094e4190b3ed8bfb8f1d7c714c676ba7c08f99dad64","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":3,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.evalFrom_append {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) (x y : List α) : M.evalFrom S (x ++ y) = M.evalFrom (M.evalFrom S x) y"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"31ebd886a0f47b17325099b6eb1e1a9521187040125bad713c22ac4edc125bda","prominence":"central","quote":{"exact":"Alternatively, w {\\displaystyle w} is accepted if δ ∗ ( q 0"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Alternatively, w {\\displaystyle w} is accepted if δ ∗ ( q 0 , w ) ∩ F ≠ ∅ {\\displaystyle \\delta ^{*}(q_{0},w)\\cap F\\not =\\emptyset } , where δ ∗ : Q × Σ ∗ → P ( Q ) {\\displaystyle \\delta ^{*}:Q\\times \\Sigma ^{*}\\rightarrow {\\mathcal {P}}(Q)} is defined recursively by: δ ∗ ( r , ε ) = { r } {\\displaystyle \\delta ^{*}(r,\\varepsilon )=\\{r\\}} where ε {\\displaystyle \\varepsilon } is the empty string, and δ ∗ ( r , x a ) = ⋃ r ′ ∈ δ ∗ ( r , x ) δ ( r ′ , a ) {\\displaystyle \\delta ^{*}(r,xa)=\\bigcup _{r'\\in \\delta ^{*}(r,x)}\\delta (r',a)} for all x ∈ Σ ∗ , a ∈ Σ {\\displaystyle x\\in \\Sigma ^{*},a\\in \\Sigma } .","segments":[{"text":"Alternatively, "},{"tex":"w"},{"text":" is accepted if "},{"tex":"\\delta ^{*}(q_{0},w)\\cap F\\not =\\emptyset"},{"text":" , where "},{"tex":"\\delta ^{*}:Q\\times \\Sigma ^{*}\\rightarrow {\\mathcal {P}}(Q)"},{"text":" is defined recursively by: "},{"tex":"\\delta ^{*}(r,\\varepsilon )=\\{r\\}"},{"text":" where "},{"tex":"\\varepsilon"},{"text":" is the empty string, and "},{"tex":"\\delta ^{*}(r,xa)=\\bigcup _{r'\\in \\delta ^{*}(r,x)}\\delta (r',a)"},{"text":" for all "},{"tex":"x\\in \\Sigma ^{*},a\\in \\Sigma"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"2d3fcdd42fd291f3175025e1266028fc0712e6f9831cf4e27cabac1acec24498","coverage":null,"id":"enwiki-653406-1366106761::In-text #cd32831e","item":"In-text #cd32831e","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_evalFrom_iff_nonempty_path","end_line":296,"library":"mathlib","line":280,"location_key":"2d3fcdd42fd291f3175025e1266028fc0712e6f9831cf4e27cabac1acec24498","module":"Mathlib.Computability.NFA","note":"Mathlib writes the set element by element and names reachability by its inductive path type, and it puts no finiteness condition on the states or the alphabet.","pair_key":"ac646eb638030c055a47230573eba257c55f31debd55f300566a9bb2971631bd","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_evalFrom_iff_nonempty_path {α : Type u} {σ : Type v} {M : NFA α σ} {s t : σ} {x : List α} : t ∈ M.evalFrom {s} x ↔ Nonempty (M.Path s t x)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"df2394fbac218cb10ae0e7834838d25c1e263e85c53661fbab6b81795fd997f9","prominence":"supporting","quote":{"exact":"In words, δ ∗ ( r , x ) {\\displaystyle \\delta ^{*}(r,x)}"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"In words, δ ∗ ( r , x ) {\\displaystyle \\delta ^{*}(r,x)} is the set of all states reachable from state r {\\displaystyle r} by consuming the string x {\\displaystyle x} .","segments":[{"text":"In words, "},{"tex":"\\delta ^{*}(r,x)"},{"text":" is the set of all states reachable from state "},{"tex":"r"},{"text":" by consuming the string "},{"tex":"x"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"f778c46c4bb17959d6949564c88cdde72c992f12c8faf6523250f5c7a8a5636a","coverage":null,"id":"enwiki-653406-1366106761::In-text #3ac66040","item":"In-text #3ac66040","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts_iff_exists_path","end_line":301,"library":"mathlib","line":298,"location_key":"f778c46c4bb17959d6949564c88cdde72c992f12c8faf6523250f5c7a8a5636a","module":"Mathlib.Computability.NFA","note":"Mathlib allows a set of start states and no finiteness condition, and the article's single start state is the singleton case.","pair_key":"a7014caf9dc5c623e1013caacee6c7112b29f3848bcfa14f8923718b15aa4deb","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"895811518eee920ba5bdb4192afab79f19050e274a5394b25d755925224e7ccf","module":"Mathlib.Computability.NFA","note":"This phrases the same criterion through the evaluated set of reached states rather than through a path.","pair_key":"8cab3d0bf596d7f0df44018736f5fb0b220679ed0f05df3b4f4b371fba3028c1","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"9255df36cebc380fe36b01b32359440ac6b7a467123366de838175f28dc1fd4a","prominence":"supporting","quote":{"exact":"The string w {\\displaystyle w} is accepted if some accepting state in"},"quote_capped":true,"section":["Formal definition","Recognized language"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The string w {\\displaystyle w} is accepted if some accepting state in F {\\displaystyle F} can be reached from the start state q 0 {\\displaystyle q_{0}} by consuming w {\\displaystyle w} .","segments":[{"text":"The string "},{"tex":"w"},{"text":" is accepted if some accepting state in "},{"tex":"F"},{"text":" can be reached from the start state "},{"tex":"q_{0}"},{"text":" by consuming "},{"tex":"w"},{"text":" ."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":4,"queries":4,"sha256":"d19b5569ece17e5a0b9bc6031c6400d9cc306747a5df31a1a453fd87004ed173"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #c67fc943","item":"In-text #c67fc943","kind":"construction","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"1e55b5337ef76bd36fb1cc63265026a811be2cfae5a7896f6b1c81fa716970c3","prominence":"supporting","quote":{"exact":"There is an easy construction that translates an NFA with multiple initial"},"quote_capped":true,"section":["Formal definition","Initial state"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"There is an easy construction that translates an NFA with multiple initial states to an NFA with a single initial state, which provides a convenient notation.","segments":[{"text":"There is an easy construction that translates an NFA with multiple initial states to an NFA with a single initial state, which provides a convenient notation."}]},"unresolved":null},{"absence":null,"basis":"832a9dca7d33787e05a2928fef56baf3ac9b9defcaef3dd7c3141cf5375cb1b8","coverage":null,"id":"enwiki-653406-1366106761::In-text #5733f4ee","item":"In-text #5733f4ee","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"DFA.reindex_apply_start","end_line":229,"library":"mathlib","line":229,"location_key":"832a9dca7d33787e05a2928fef56baf3ac9b9defcaef3dd7c3141cf5375cb1b8","module":"Mathlib.Computability.DFA","note":"The lemma is stated for deterministic automata, which the article itself counts among its automata, and for the particular second automaton obtained by relabelling along the bijection.","pair_key":"9043038b186eb2df55a8ab21a2387255c494acc71ee601d964c93e7d680ccf84","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":1,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.reindex_apply_start {α : Type u} {σ : Type v} {σ' : Type*} (g : σ ≃ σ') (M : DFA α σ) : ((DFA.reindex g) M).start = g M.start"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"DFA.reindex_apply_accept","end_line":229,"library":"mathlib","line":229,"location_key":"29ede8f593a1a9648c05a10479c770293b6c852423d47369f862e58c18b43fc3","module":"Mathlib.Computability.DFA","note":"The accepting set of the relabelled automaton is described as the preimage along the inverse bijection, which is the article's two-way condition on accepting states.","pair_key":"0c016b1c9e34bcfade8028eab028b4fd9898d3d3def4551e97e6140ae4d9b40e","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":2,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.reindex_apply_accept {α : Type u} {σ : Type v} {σ' : Type*} (g : σ ≃ σ') (M : DFA α σ) : ((DFA.reindex g) M).accept = ⇑g.symm ⁻¹' M.accept"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"DFA.reindex_apply_step","end_line":229,"library":"mathlib","line":229,"location_key":"472f0554bc41a0114b8f71474d257982dc0840b57a3dca1436b54bb751d8c421","module":"Mathlib.Computability.DFA","note":"For deterministic automata the transition set is a single state, so the equation between the two transition functions is the article's two-way condition on transitions.","pair_key":"27dd516f4bb555409aa57741cbcfb8498c743108b54a41ba0b0b2f70ef2a001a","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":3,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.reindex_apply_step {α : Type u} {σ : Type v} {σ' : Type*} (g : σ ≃ σ') (M : DFA α σ) (s : σ') (a : α) : ((DFA.reindex g) M).step s a = g (M.step (g.symm s) a)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"5870ac1a825b8b4f91e7c3c24b9dc5982e7a5aadc46ad89683d52b8c3b2d0140","prominence":"central","quote":{"exact":"φ ( q 0 ) = q 0 ′ {\\displaystyle \\varphi (q_{0})=q'_{0}}"},"quote_capped":true,"section":["Formal definition","Isomorphism"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"An isomorphism φ {\\displaystyle \\varphi } from an automaton ( Q , Σ , δ , q 0 , F ) {\\displaystyle (Q,\\Sigma ,\\delta ,q_{0},F)} to an automaton ( Q ′ , Σ , δ ′ , q 0 ′ , F ′ ) {\\displaystyle (Q',\\Sigma ,\\delta ',q'_{0},F')} is a bijective mapping φ : Q → Q ′ {\\displaystyle \\varphi :Q\\to Q'} such that ","lead_in":true,"segments":[{"text":"An isomorphism "},{"tex":"\\varphi"},{"text":" from an automaton "},{"tex":"(Q,\\Sigma ,\\delta ,q_{0},F)"},{"text":" to an automaton "},{"tex":"(Q',\\Sigma ,\\delta ',q'_{0},F')"},{"text":" is a bijective mapping "},{"tex":"\\varphi :Q\\to Q'"},{"text":" such that "}]},"layer":"φ ( q 0 ) = q 0 ′ {\\displaystyle \\varphi (q_{0})=q'_{0}} , q ∈ F {\\displaystyle q\\in F} if, and only if, φ ( q ) ∈ F ′ {\\displaystyle \\varphi (q)\\in F'} , for each q ∈ Q {\\displaystyle q\\in Q} , and r ∈ δ ( q , a ) {\\displaystyle r\\in \\delta (q,a)} if, and only if, φ ( r ) ∈ δ ′ ( φ ( q ) , a ) {\\displaystyle \\varphi (r)\\in \\delta '(\\varphi (q),a)} , for each q , r ∈ Q {\\displaystyle q,r\\in Q} and a ∈ Σ {\\displaystyle a\\in \\Sigma } .","segments":[{"tex":"\\varphi (q_{0})=q'_{0}"},{"text":" , "},{"tex":"q\\in F"},{"text":" if, and only if, "},{"tex":"\\varphi (q)\\in F'"},{"text":" , for each "},{"tex":"q\\in Q"},{"text":" , and "},{"tex":"r\\in \\delta (q,a)"},{"text":" if, and only if, "},{"tex":"\\varphi (r)\\in \\delta '(\\varphi (q),a)"},{"text":" , for each "},{"tex":"q,r\\in Q"},{"text":" and "},{"tex":"a\\in \\Sigma"},{"text":" ."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"96c0d1109fb63a8ad072da5d0f886b67034b5237ef1e20077df1301af94e16ba"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #f6672c32","item":"In-text #f6672c32","kind":"example","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"737a4fe55a4f56a63308fc2a3ed6be4ae25645c088902c68e707bbc0e044ce4c","prominence":"supporting","quote":{"exact":"The following automaton M, with a binary alphabet, determines if the input"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The following automaton M, with a binary alphabet, determines if the input ends with a 1.","segments":[{"text":"The following automaton M, with a binary alphabet, determines if the input ends with a 1."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"339a0e30cb4708d39a6febdf6aea6f86bb840535ad6b10cb42b4b0c56c0d00f9"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #c9abbf55","item":"In-text #c9abbf55","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"923d36babaef48a8c486d854c13efed48d7ff9b30434f389e97ec8465309fa92","prominence":"supporting","quote":{"exact":"M is nondeterministic."},"quote_capped":false,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"Since the set δ ( p , 1 ) {\\displaystyle \\delta (p,1)} contains more than one state, ","segments":[{"text":"Since the set "},{"tex":"\\delta (p,1)"},{"text":" contains more than one state, "}]},"layer":"M is nondeterministic.","segments":[{"text":"M is nondeterministic."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"0a67d3369bd950352f0b9029ea070e32506fd959c435b6bbec323f222a656d13"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #9d9904e3","item":"In-text #9d9904e3","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"f990a72a75bc43239a864b558ae97346e55108364e704cdf250eb4f103d04b63","prominence":"supporting","quote":{"exact":"The language of M can be described by the regular language given"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The language of M can be described by the regular language given by the regular expression (0|1)*1.","segments":[{"text":"The language of M can be described by the regular language given by the regular expression (0|1)*1."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"9b01628c69829aa6836a258b8e2642b8132fb130cd64fc64f4166a076ad3704a"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #51df03bb","item":"In-text #51df03bb","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"6a87465c8308c587d69f6f2163ef4030aa03509872b35c93fb778f2d040813b6","module":"Mathlib.Computability.NFA","note":"It is the acceptance test for an arbitrary automaton and an arbitrary word; it fixes no transition table, so the verdict on this two-state machine and this word is beyond what it says.","pair_key":"28fbe8d5643a886422bbc02207b3516676b37312941829d74aba5ea3010ec2e5","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"99fcd220c639ef782aca5630bb95e7a788e41e563d489bb74abdf3500c5cb729","prominence":"supporting","quote":{"exact":"The string is accepted by M"},"quote_capped":false,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" since one state sequence satisfies the above definition; it does not matter that other sequences fail to do so.","segments":[{"text":" since one state sequence satisfies the above definition; it does not matter that other sequences fail to do so."}]},"layer":"The string is accepted by M","segments":[{"text":"The string is accepted by M"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"b465e3b35a2af2def37ed9e0991694d5a4c232587ad850391af0f2c82512b05f"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #68324597","item":"In-text #68324597","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts_iff_exists_path","end_line":301,"library":"mathlib","line":298,"location_key":"db5ecabebadebb60eed5ae5d3cae14c52e7bcfd8a3d5142db79ef38f3da03dcf","module":"Mathlib.Computability.NFA","note":"This is the run-based reading of acceptance for an arbitrary automaton: a word is in the language exactly when some run joins a start state to an accepting one. It settles no concrete machine.","pair_key":"d45369de5cf9eb216891e437d0bd27f8a2430c27671193721c34a6b8761b0d73","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.accepts_iff_exists_path {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ s ∈ M.start, ∃ t ∈ M.accept, Nonempty (M.Path s t x)"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"d6e29e74804a2b0fc988f19154f7adaba7ec3a051a6e4cd5e7190a88f57fa09d","prominence":"supporting","quote":{"exact":"Considering the first of the above formal definitions, \"1011\" is accepted"},"quote_capped":false,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" since when reading it M may traverse the state sequence ⟨ r 0 , r 1 , r 2 , r 3 , r 4 ⟩ = ⟨ p , p , p , p , q ⟩ {\\displaystyle \\langle r_{0},r_{1},r_{2},r_{3},r_{4}\\rangle =\\langle p,p,p,p,q\\rangle } , which satisfies conditions 1 to 3.","segments":[{"text":" since when reading it M may traverse the state sequence "},{"tex":"\\langle r_{0},r_{1},r_{2},r_{3},r_{4}\\rangle =\\langle p,p,p,p,q\\rangle"},{"text":" , which satisfies conditions 1 to 3."}]},"layer":"Considering the first of the above formal definitions, \"1011\" is accepted","segments":[{"text":"Considering the first of the above formal definitions, \"1011\" is accepted"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"a46218a63ee3c6fdf78bc103f31e04960e799bfe07eccedd4c94a1174e04722a"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #5cd71600","item":"In-text #5cd71600","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.Path","end_line":272,"library":"mathlib","line":269,"location_key":"0058416629e8d3a96d8f8c299b329a664e5f4c6fad44f6b395146b26ab47f137","module":"Mathlib.Computability.NFA","note":"The inductive family of concrete runs of an arbitrary automaton between two states for a given word; it is the vocabulary in which the passage's run would be written, not an assertion that this run exists.","pair_key":"e8d4b4a97ef0dee7f0ecf7de9b7c1019c9d5cb7644ebdda5b23e92deb9a03f3b","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"inductive NFA.Path {α : Type u} {σ : Type v} : NFA α σ → σ → σ → List α → Type (max u v)"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"6204ec50d5975050a86a0743685d6440af3d821a636d3084a93569f8299fd26e","prominence":"supporting","quote":{"exact":"when reading it M may traverse the state sequence ⟨ r 0"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"Considering the first of the above formal definitions, \"1011\" is accepted since ","segments":[{"text":"Considering the first of the above formal definitions, \"1011\" is accepted since "}]},"layer":"when reading it M may traverse the state sequence ⟨ r 0 , r 1 , r 2 , r 3 , r 4 ⟩ = ⟨ p , p , p , p , q ⟩ {\\displaystyle \\langle r_{0},r_{1},r_{2},r_{3},r_{4}\\rangle =\\langle p,p,p,p,q\\rangle } , which satisfies conditions 1 to 3.","segments":[{"text":"when reading it M may traverse the state sequence "},{"tex":"\\langle r_{0},r_{1},r_{2},r_{3},r_{4}\\rangle =\\langle p,p,p,p,q\\rangle"},{"text":" , which satisfies conditions 1 to 3."}]},"unresolved":null},{"absence":null,"basis":"a449df83fb0077a12f432c5c240634abc10d14eb4eeb2c1d0c480e1f0b304b61","coverage":null,"id":"enwiki-653406-1366106761::In-text #38b9ff36","item":"In-text #38b9ff36","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.evalFrom_nil","end_line":103,"library":"mathlib","line":102,"location_key":"a449df83fb0077a12f432c5c240634abc10d14eb4eeb2c1d0c480e1f0b304b61","module":"Mathlib.Computability.NFA","note":"The lemma holds for every automaton and every set of starting states, so the passage's case is one instance; mathlib's evalFrom reads a set of states where the article writes the single state p, and the matching set is {p}.","pair_key":"723f1eb83038488954d13e714292289937187fb8536f8472d9d33b89a00cc2ea","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.evalFrom_nil {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) : M.evalFrom S [] = S"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.eval_nil","end_line":238,"library":"mathlib","line":237,"location_key":"52be15222e2d7497fe6d95e2084cb0809d8e8267bc53cf92e9ae6641b50160c3","module":"Mathlib.Computability.NFA","note":"mathlib's eval runs a word from the machine's own start states; for this machine that set is the singleton of p, and the lemma at the empty word returns it unchanged.","pair_key":"692cd0db763339ba27861bed0491e2db135ec6869be4bf34b6664f55dabb298e","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.eval_nil {α : Type u} {σ : Type v} (M : NFA α σ) : M.eval [] = M.start"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"cf54f62746927aab9eeba4410df842a1be9bb69a4facaafbccb640ba2c9a5414","prominence":"supporting","quote":{"exact":"Concerning the second formal definition, bottom-up computation shows that δ ∗ ("},"quote_capped":true,"section":["Example"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" , hence δ ∗ ( p , 1 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}} , hence δ ∗ ( p , 10 ) = δ ( p , 0 ) ∪ δ ( q , 0 ) = { p } ∪ { } {\\displaystyle \\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}} , hence δ ∗ ( p , 101 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}}","segments":[{"text":" , hence "},{"tex":"\\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}"}],"trimmed":true},"layer":"Concerning the second formal definition, bottom-up computation shows that δ ∗ ( p , ε ) = { p } {\\displaystyle \\delta ^{*}(p,\\varepsilon )=\\{p\\}}","segments":[{"text":"Concerning the second formal definition, bottom-up computation shows that "},{"tex":"\\delta ^{*}(p,\\varepsilon )=\\{p\\}"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"6769c379a421ddaeb3dab60b23101b43a9994f457a825ea2c72693553e9246c6"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #89385fb7","item":"In-text #89385fb7","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.evalFrom_singleton","end_line":108,"library":"mathlib","line":107,"location_key":"41afe584c42bbe0094bbe6c6fe893eea2080d817ab3f7d4fd8bd734182077d46","module":"Mathlib.Computability.NFA","note":"For any automaton and any starting set it rewrites a one-letter word as a single transition step; that is the intermediate move of the displayed chain, while the value the chain ends at is read off this machine's table.","pair_key":"7889a2c27aef936f40ea97e766a0e10793ad9a76ad603aace662cebef9754a2e","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.evalFrom_singleton {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) (a : α) : M.evalFrom S [a] = M.stepSet S a"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.stepSet_singleton","end_line":85,"library":"mathlib","line":84,"location_key":"64a96d6797f4ab737d9037011ec88ceb0d2389bda709ffe78e4fc780dfe84176","module":"Mathlib.Computability.NFA","note":"A step from a one-element set of states is the transition of that state, for any automaton; the pair of states the passage records comes from this machine's table instead.","pair_key":"76dede3c1a607c5cc7fe610177f323a116c1f0758601819473507a0f502ac123","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.stepSet_singleton {α : Type u} {σ : Type v} (M : NFA α σ) (s : σ) (a : α) : M.stepSet {s} a = M.step s a"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"2867c644534696bf960a0a940c3ca1160c2f0032fc1b03c49f159bb61f4eff1e","prominence":"supporting","quote":{"exact":"δ ∗ ( p , 1 ) = δ ( p ,"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" , hence δ ∗ ( p , 10 ) = δ ( p , 0 ) ∪ δ ( q , 0 ) = { p } ∪ { } {\\displaystyle \\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}} , hence δ ∗ ( p , 101 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}} , and hence δ ∗ ( p , 1011 ) = δ ( p , 1 ) ∪ δ ( q , 1 ) = { p , q } ∪ { } {\\displaystyle \\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}}","segments":[{"text":" , hence "},{"tex":"\\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}"},{"text":" , and hence "},{"tex":"\\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}"}],"trimmed":true},"before":{"layer":"Concerning the second formal definition, bottom-up computation shows that δ ∗ ( p , ε ) = { p } {\\displaystyle \\delta ^{*}(p,\\varepsilon )=\\{p\\}} , hence ","segments":[{"text":"Concerning the second formal definition, bottom-up computation shows that "},{"tex":"\\delta ^{*}(p,\\varepsilon )=\\{p\\}"},{"text":" , hence "}]},"layer":"δ ∗ ( p , 1 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}}","segments":[{"tex":"\\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"7827ee2a7dd74dcde76adc95e4e60f646e35976c89875766f981e15b8542bc80"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #dd2f91a5","item":"In-text #dd2f91a5","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.evalFrom_append","end_line":120,"library":"mathlib","line":118,"location_key":"21d96035e04ae92cececb36a8f410906910b38628760a67d49f8e141925c69a1","module":"Mathlib.Computability.NFA","note":"It splits a word in two and runs the pieces in turn, for any automaton and starting set; that recursion is how the article moves from one prefix to the next, but the sets it lands in come from this machine's table.","pair_key":"52d11db5d7ec2d2e524f623737215fba749e6f56f6adf741f1879fa3e3c996ca","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.evalFrom_append {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) (x y : List α) : M.evalFrom S (x ++ y) = M.evalFrom (M.evalFrom S x) y"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.stepSet","end_line":73,"library":"mathlib","line":72,"location_key":"62e1badccef13ec8853dbca0422664ec7c79406eeb590bd64cdabacba643e9fd","module":"Mathlib.Computability.NFA","note":"The definition of one step from a set of states as the union of the transitions of its members, for any automaton; the union the passage displays is an instance of that shape with values this machine's table supplies.","pair_key":"674277b30a4faa9c2c33ead53d217e81883d6033c30ffc22ab16e4dd9363aa34","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.stepSet {α : Type u} {σ : Type v} : NFA α σ → Set σ → α → Set σ"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"7611b3247af6ba0d85b426a55d333742d12e8878af946c55130096b9dbd97be9","prominence":"supporting","quote":{"exact":"δ ∗ ( p , 10 ) = δ ( p ,"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" , hence δ ∗ ( p , 101 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}} , and hence δ ∗ ( p , 1011 ) = δ ( p , 1 ) ∪ δ ( q , 1 ) = { p , q } ∪ { } {\\displaystyle \\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}} ; since that set is not disjoint from { q } {\\displaystyle \\{q\\}}","segments":[{"text":" , hence "},{"tex":"\\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}"},{"text":" , and hence "},{"tex":"\\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}"},{"text":" ; since that set is not disjoint from "},{"tex":"\\{q\\}"}],"trimmed":true},"before":{"layer":"Concerning the second formal definition, bottom-up computation shows that δ ∗ ( p , ε ) = { p } {\\displaystyle \\delta ^{*}(p,\\varepsilon )=\\{p\\}} , hence δ ∗ ( p , 1 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}} , hence ","segments":[{"text":"Concerning the second formal definition, bottom-up computation shows that "},{"tex":"\\delta ^{*}(p,\\varepsilon )=\\{p\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}"},{"text":" , hence "}]},"layer":"δ ∗ ( p , 10 ) = δ ( p , 0 ) ∪ δ ( q , 0 ) = { p } ∪ { } {\\displaystyle \\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}}","segments":[{"tex":"\\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"300f90fa9f16ad577e964d379d841b19e1526495e66e833b26d3a51f8daa6796"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #590e7cce","item":"In-text #590e7cce","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.evalFrom_append","end_line":120,"library":"mathlib","line":118,"location_key":"346c77c92089170800b2025ce3e27df3c06d224d2356c719e3236453c1ccbe14","module":"Mathlib.Computability.NFA","note":"For any automaton it runs a word prefix first and the rest afterwards, which is the recursion carrying the article from the prefix 10 to the prefix 101; the resulting states are those this machine's table gives.","pair_key":"9a4b6725e60389f1b5317f7f2299d870e6026f1c165ea60a6ccb673d0840e543","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.evalFrom_append {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) (x y : List α) : M.evalFrom S (x ++ y) = M.evalFrom (M.evalFrom S x) y"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.stepSet_singleton","end_line":85,"library":"mathlib","line":84,"location_key":"86e31449691610eaa7f70b763a248252dbca5a302d5e533b5e161210dbf1a74f","module":"Mathlib.Computability.NFA","note":"A step from a one-element set of states is that state's transition, for any automaton; which pair of states the letter 1 then yields is settled by the table the article displays.","pair_key":"593fce4aba73ec2909d21042fb9c8f6d3a2d1700dc05082076b409f6e22983f8","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.stepSet_singleton {α : Type u} {σ : Type v} (M : NFA α σ) (s : σ) (a : α) : M.stepSet {s} a = M.step s a"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"4510706dfd90a9fd767146e475637a9732e7dd41e0d97732ddb08ffbe89844c9","prominence":"supporting","quote":{"exact":"δ ∗ ( p , 101 ) = δ ( p ,"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" , and hence δ ∗ ( p , 1011 ) = δ ( p , 1 ) ∪ δ ( q , 1 ) = { p , q } ∪ { } {\\displaystyle \\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}} ; since that set is not disjoint from { q } {\\displaystyle \\{q\\}} , the string \"1011\" is accepted.","segments":[{"text":" , and hence "},{"tex":"\\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}"},{"text":" ; since that set is not disjoint from "},{"tex":"\\{q\\}"},{"text":" , the string \"1011\" is accepted."}]},"before":{"layer":"δ ∗ ( p , ε ) = { p } {\\displaystyle \\delta ^{*}(p,\\varepsilon )=\\{p\\}} , hence δ ∗ ( p , 1 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}} , hence δ ∗ ( p , 10 ) = δ ( p , 0 ) ∪ δ ( q , 0 ) = { p } ∪ { } {\\displaystyle \\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}} , hence ","segments":[{"tex":"\\delta ^{*}(p,\\varepsilon )=\\{p\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}"},{"text":" , hence "}],"trimmed":true},"layer":"δ ∗ ( p , 101 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}}","segments":[{"tex":"\\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}"}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"70417acfe8e7af8fe03433cbb1688f08e848b8890b7e27188ab591c42b46208d"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #da7162ce","item":"In-text #da7162ce","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.evalFrom_append","end_line":120,"library":"mathlib","line":118,"location_key":"663b0adebd06443fa08b52e935b3fca0654fd4fe0ff96a4c7c63b71506013fee","module":"Mathlib.Computability.NFA","note":"For any automaton it runs a prefix and then the remaining letter, which is the recursion that takes the article from 101 to the full word; the sets it names come from this machine's table.","pair_key":"6bb40415d0a51d7668f733a4754522c1cdc026bcf664d9b84a6285dae3061eb8","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.evalFrom_append {α : Type u} {σ : Type v} (M : NFA α σ) (S : Set σ) (x y : List α) : M.evalFrom S (x ++ y) = M.evalFrom (M.evalFrom S x) y"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.stepSet_union","end_line":92,"library":"mathlib","line":89,"location_key":"4e1e8c1c5dca0a80837c70254017e4571f105d60615717cce9835b09c3311e74","module":"Mathlib.Computability.NFA","note":"A step from a union of two sets of states is the union of the two steps, for any automaton; the union the passage displays has that shape, with values read off this machine's table.","pair_key":"ede14e8da5c68ce0d6f037dffc9bc04335674bf1c69ca85dada7e40f1aecd2f5","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.stepSet_union {α : Type u} {σ : Type v} (M : NFA α σ) {S T : Set σ} {a : α} : M.stepSet (S ∪ T) a = M.stepSet S a ∪ M.stepSet T a"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"3eea6fc331076419d9e660b363cf2ddb92f15f3d8dff14ebdf4d90d95da94089","prominence":"supporting","quote":{"exact":"δ ∗ ( p , 1011 ) = δ ( p ,"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" ; since that set is not disjoint from { q } {\\displaystyle \\{q\\}} , the string \"1011\" is accepted.","segments":[{"text":" ; since that set is not disjoint from "},{"tex":"\\{q\\}"},{"text":" , the string \"1011\" is accepted."}]},"before":{"layer":"δ ∗ ( p , 1 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}} , hence δ ∗ ( p , 10 ) = δ ( p , 0 ) ∪ δ ( q , 0 ) = { p } ∪ { } {\\displaystyle \\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}} , hence δ ∗ ( p , 101 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}} , and hence ","segments":[{"tex":"\\delta ^{*}(p,1)=\\delta (p,1)=\\{p,q\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,10)=\\delta (p,0)\\cup \\delta (q,0)=\\{p\\}\\cup \\{\\}"},{"text":" , hence "},{"tex":"\\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}"},{"text":" , and hence "}],"trimmed":true},"layer":"δ ∗ ( p , 1011 ) = δ ( p , 1 ) ∪ δ ( q , 1 ) = { p , q } ∪ { } {\\displaystyle \\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}}","segments":[{"tex":"\\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"af1492217306822ecb2b66ddfaebeef52dab83b5b004a2b2872a6a44ed0cf023"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #138fad1c","item":"In-text #138fad1c","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"5be39f003bfdd450ad275d7df38486c982e2de595b9c167c1e5dabee8152611f","module":"Mathlib.Computability.NFA","note":"It is the general acceptance test, not a claim about the article's machine.","pair_key":"881195f739a530ea4d9a7c1ba42d700e240a6f94c82827e5c5aaca5c873d5154","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"a2c53dee76533dd1348308dc811a43c17defdf58671619fe30c920dc81d86752","prominence":"supporting","quote":{"exact":"the string \"1011\" is accepted."},"quote_capped":false,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"δ ∗ ( p , 101 ) = δ ( p , 1 ) = { p , q } {\\displaystyle \\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}} , and hence δ ∗ ( p , 1011 ) = δ ( p , 1 ) ∪ δ ( q , 1 ) = { p , q } ∪ { } {\\displaystyle \\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}} ; since that set is not disjoint from { q } {\\displaystyle \\{q\\}} , ","segments":[{"tex":"\\delta ^{*}(p,101)=\\delta (p,1)=\\{p,q\\}"},{"text":" , and hence "},{"tex":"\\delta ^{*}(p,1011)=\\delta (p,1)\\cup \\delta (q,1)=\\{p,q\\}\\cup \\{\\}"},{"text":" ; since that set is not disjoint from "},{"tex":"\\{q\\}"},{"text":" , "}],"trimmed":true},"layer":"the string \"1011\" is accepted.","segments":[{"text":"the string \"1011\" is accepted."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"4e218359928d60f0dd4841c6a0be02147459fcdf4754960e3109cb2a84b64316"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #a60f49bc","item":"In-text #a60f49bc","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"528c0c3bce339a31928dd336fb68a207fad0096927fc722fc6640309e0fe1523","module":"Mathlib.Computability.NFA","note":"Its negation would express rejection, but only for an arbitrary automaton.","pair_key":"702363daf93ea64d3fbfa604a54254c2379625652b7ee63f7b4e7fd59bd4586a","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"94789452dc3c554440dc49df919615bc31d9a07d0abb53ace51c930bdd4d7d16","prominence":"supporting","quote":{"exact":"In contrast, the string \"10\" is rejected by M"},"quote_capped":false,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" (all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state, q, by reading the final 0 symbol.","segments":[{"text":" (all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state, q, by reading the final 0 symbol."}]},"layer":"In contrast, the string \"10\" is rejected by M","segments":[{"text":"In contrast, the string \"10\" is rejected by M"}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":2,"queries":4,"sha256":"e6f1746b558afc44730e08feb1de0c8e16c4bd361c89df3a36a54226418506ff"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #49214479","item":"In-text #49214479","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_stepSet","end_line":76,"library":"mathlib","line":75,"location_key":"333c31f1e7ff33f0fd09365195fdd5f67f7a732a7f5ab9febaf4a76ff0ac0889","module":"Mathlib.Computability.NFA","note":"It unfolds which states one step on a symbol can reach, for any automaton.","pair_key":"00a1053f2831a4ab320d8d9ed989b6c7b069ca085ee0dbdcbefc5a775cd9a966","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_stepSet {α : Type u} {σ : Type v} {M : NFA α σ} {s : σ} {S : Set σ} {a : α} : s ∈ M.stepSet S a ↔ ∃ t ∈ S, s ∈ M.step t a"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"c9f62759f058a24fab42b1ea68de13066329c29f73950ceb1fcafab48d3e57f5","prominence":"supporting","quote":{"exact":"there is no way to reach the only accepting state, q, by"},"quote_capped":true,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"In contrast, the string \"10\" is rejected by M (all possible state sequences for that input are shown in the upper right picture), since ","segments":[{"text":"In contrast, the string \"10\" is rejected by M (all possible state sequences for that input are shown in the upper right picture), since "}]},"layer":"there is no way to reach the only accepting state, q, by reading the final 0 symbol.","segments":[{"text":"there is no way to reach the only accepting state, q, by reading the final 0 symbol."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"9152454b4e979d6d71e7002feddfb537654e14919c0f16faf5b031567ee99154"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #40a34114","item":"In-text #40a34114","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"6a8e989b4ed3e733e567138cb5ece81c25dd5b63517771d240bebe256792c406","module":"Mathlib.Computability.NFA","note":"It is the general acceptance test applied to any word, including one-letter words.","pair_key":"86193fa72e376346f2ee67d68b3b88591dad7efa7c2220a3f9204f81ccd476e5","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"b5b1ff122379bf72091e706bf7e547dfe64694d9f2209c02a109c955644c769e","prominence":"supporting","quote":{"exact":"rather, it means that an input string \"1\" would be accepted."},"quote_capped":false,"section":["Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"While q can be reached after consuming the initial \"1\", this does not mean that the input \"10\" is accepted; ","segments":[{"text":"While q can be reached after consuming the initial \"1\", this does not mean that the input \"10\" is accepted; "}]},"layer":"rather, it means that an input string \"1\" would be accepted.","segments":[{"text":"rather, it means that an input string \"1\" would be accepted."}]},"unresolved":null},{"absence":null,"basis":"9d286ba7bc88c7cc5fc4a2a4940eb45cf9c5326fb63141dd73d92bc886b26cfb","coverage":null,"id":"enwiki-653406-1366106761::In-text #96401e50","item":"In-text #96401e50","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA","end_line":334,"library":"mathlib","line":331,"location_key":"9d286ba7bc88c7cc5fc4a2a4940eb45cf9c5326fb63141dd73d92bc886b26cfb","module":"Mathlib.Computability.NFA","note":"The construction keeps the start state and the accept set and sends each state and symbol to the one element set holding the deterministic successor.","pair_key":"bf0477282011241bb73bb4137c3db0950507608253b7e134ef19c499cbf38add","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":1,"relation":"exactMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def DFA.toNFA {α : Type u} {σ : Type v} : DFA α σ → NFA α σ"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA_step","end_line":331,"library":"mathlib","line":331,"location_key":"506cb12a89d09670b85472ee31100da6783d088e03202b56b9ccfdfca82e399e","module":"Mathlib.Computability.NFA","note":"The theorem unfolds the transition of the associated NFA to the one element set holding the deterministic successor.","pair_key":"16c92ade9f10e711f9e0284a1e522b406b290514759a802d060b1ca529603272","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"closeMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.toNFA_step {α : Type u} {σ : Type v} (M : DFA α σ) (s : σ) (a : α) : M.toNFA.step s a = {M.step s a}"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"17b74d0f43e74932d6219efe348584956b87944d71856f4d4a402b987d860e3e","prominence":"central","quote":{"exact":"A deterministic finite automaton (DFA) can be seen as a special kind"},"quote_capped":true,"section":["Equivalence to DFA"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"A deterministic finite automaton (DFA) can be seen as a special kind of NFA, in which for each state and symbol, the transition function has exactly one state.","segments":[{"text":"A deterministic finite automaton (DFA) can be seen as a special kind of NFA, in which for each state and symbol, the transition function has exactly one state."}]},"unresolved":null},{"absence":null,"basis":"830ec2027cc5259cd9eb746cb6257c13a84dea7883473b2c10af5e990f0ca594","coverage":null,"id":"enwiki-653406-1366106761::In-text #cbcfd9d7","item":"In-text #cbcfd9d7","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA_correct","end_line":354,"library":"mathlib","line":348,"location_key":"830ec2027cc5259cd9eb746cb6257c13a84dea7883473b2c10af5e990f0ca594","module":"Mathlib.Computability.NFA","note":"The theorem names an explicit witness automaton for each deterministic one and equates the two recognised languages.","pair_key":"e4b5709c7f999074a7bcadcbd96e765aaa02c34d027cc314c3c0e9f9c87d60cc","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA","end_line":334,"library":"mathlib","line":331,"location_key":"92e6379972785b2e22c408a9d253b6a162808f3e3944a7da4f6f409fd349d21b","module":"Mathlib.Computability.NFA","note":"It supplies the witness automaton but makes no claim about languages.","pair_key":"c03747664c85c3e065f896097a9ee7eebd87b0b3ddfa53a171871ab6b64b5ab9","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def DFA.toNFA {α : Type u} {σ : Type v} : DFA α σ → NFA α σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"6b8e32a3efa7b0126f89ea8686ecc347433600cd1bcfa13a27bbd541f0d1ac8e","prominence":"central","quote":{"exact":"Thus, it is clear that every formal language that can be recognized"},"quote_capped":true,"section":["Equivalence to DFA"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Thus, it is clear that every formal language that can be recognized by a DFA can be recognized by an NFA.","segments":[{"text":"Thus, it is clear that every formal language that can be recognized by a DFA can be recognized by an NFA."}]},"unresolved":null},{"absence":null,"basis":"002ca5ffb9bcdbd48d30dc1fe9096365e47009359ffdd9dcad9b86cf190b4b5d","coverage":null,"id":"enwiki-653406-1366106761::In-text #44a1d3c6","item":"In-text #44a1d3c6","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA_correct","end_line":315,"library":"mathlib","line":312,"location_key":"002ca5ffb9bcdbd48d30dc1fe9096365e47009359ffdd9dcad9b86cf190b4b5d","module":"Mathlib.Computability.NFA","note":"The theorem equates the language of the subset construction automaton with the language of the given nondeterministic one.","pair_key":"55db7e507834519f870efe32459b82c4dfcfa680731ca95b69186cfed5717727","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA","end_line":309,"library":"mathlib","line":306,"location_key":"723e5e9229b5f99c4de840ff8a5e353ca414241ca643d2d1de9d6ad448d11080","module":"Mathlib.Computability.NFA","note":"It is the subset construction itself, with no claim about languages.","pair_key":"f28f2e3bba9a24c7cfa7a086fba435993bfcece6b47f1de0e67f33b0b0cf1f2d","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"8bbad1ce934121cea1145bcd0fd311f6a273088a7bd64214b3ef41ec2a7dd864","prominence":"central","quote":{"exact":"Conversely, for each NFA, there is a DFA such that it recognizes"},"quote_capped":true,"section":["Equivalence to DFA"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Conversely, for each NFA, there is a DFA such that it recognizes the same formal language.","segments":[{"text":"Conversely, for each NFA, there is a DFA such that it recognizes the same formal language."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":0,"queries":4,"sha256":"4f544fd6aad203440c22a34d2cc0ac89cd80c8b5346ab94f109ba5b64ad13ef3"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #ce96fcfe","item":"In-text #ce96fcfe","kind":"theorem","locations":[{"challenge":"downgraded","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"Fintype.card_set","end_line":69,"library":"mathlib","line":68,"location_key":"f0a751123f7da6a093e10458cc6dd9445fb34c961b01482f67ca017c7bb6af2c","module":"Mathlib.Data.Fintype.Powerset","note":"The theorem counts the sets of states of a finite state type, and that count is the number of states of the automaton the subset construction produces.","pair_key":"d9e8dbf56483725f9283230fd9eb16a2a3eb1771070358ab038d89774f70b242","path":"Mathlib/Data/Fintype/Powerset.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem Fintype.card_set {α : Type*} [Fintype α] : Fintype.card (Set α) = 2 ^ Fintype.card α"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA","end_line":309,"library":"mathlib","line":306,"location_key":"7c011c0babf26d045ca989c5773d18912ed91fa47b0caabb69ac20323de4b77a","module":"Mathlib.Computability.NFA","note":"Its type shows the built automaton has sets of states as states, with no count attached.","pair_key":"7a1701bee36b69d31298311ea96a4f01a48c3f060743fed78ae8b64744eda2af","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"e14dff704824df530550641a51e9b9523381b874c20c75d54ddcc0e9538c8c47","prominence":"supporting","quote":{"exact":"However, if the NFA has n states, the resulting DFA may have"},"quote_capped":true,"section":["Equivalence to DFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"However, if the NFA has n states, the resulting DFA may have up to 2n states, which sometimes makes the construction impractical for large NFAs.","segments":[{"text":"However, if the NFA has n states, the resulting DFA may have up to 2n states, which sometimes makes the construction impractical for large NFAs."}]},"unresolved":null},{"absence":null,"basis":"f5463bbcf31b077594bc0d037a0dcf8e1921f2cf24b4afc8dc3cf50da1d8e7fe","coverage":null,"id":"enwiki-653406-1366106761::In-text #64e4d3ed","item":"In-text #64e4d3ed","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.toεNFA_correct","end_line":352,"library":"mathlib","line":350,"location_key":"f5463bbcf31b077594bc0d037a0dcf8e1921f2cf24b4afc8dc3cf50da1d8e7fe","module":"Mathlib.Computability.EpsilonNFA","note":"The theorem is stated about the canonical conversion, over arbitrary state and alphabet types, and says the accepted language is unchanged.","pair_key":"e1852589d199e10ad1a958a14b0e953f621798e20106f4c5c2e015f516e88195","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toεNFA_correct {α : Type u} {σ : Type v} (M : NFA α σ) : M.toεNFA.accepts = M.accepts"},"statement":false},{"challenge":"downgraded","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.toεNFA","end_line":330,"library":"mathlib","line":327,"location_key":"631d587164dda81bb9e5de43628991f68a418793231da9a99b49036650dfcdc7","module":"Mathlib.Computability.EpsilonNFA","note":"This is only the conversion map; on its own it does not record that the two machines accept the same words.","pair_key":"2501e181146388a0438774046ee9bd98f08614029bf2c3423bbaa03920afecae","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.toεNFA {α : Type u} {σ : Type v} : NFA α σ → εNFA α σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"00550000c073a116b2829d1d85c87e0a46b90e6f0c9a8d2f8a652c5ce0e73706","prominence":"central","quote":{"exact":"Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA."},"quote_capped":false,"section":["NFA with ε-moves"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA.","segments":[{"text":"Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA."}]},"unresolved":null},{"absence":null,"basis":"9701aa10adf35d83cd954468b677f960e91392e55168381244c389d36adba1f3","coverage":null,"id":"enwiki-653406-1366106761::In-text #bbe556cd","item":"In-text #bbe556cd","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA","end_line":48,"library":"mathlib","line":40,"location_key":"9701aa10adf35d83cd954468b677f960e91392e55168381244c389d36adba1f3","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib gives the transition field the domain of a state together with an optional symbol, and the absent symbol is the epsilon move.","pair_key":"bebea0f59ebcc53db2f3d88ef317248f477702b00190ecb4090a78157878a0a9","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"structure εNFA : Type u → Type v → Type (max u v)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"3797c738972b6812d594bf3a7100966054cf87e11cf212a720f6311976d5a559","prominence":"central","quote":{"exact":"In this kind of automaton, the transition function is additionally defined on"},"quote_capped":true,"section":["NFA with ε-moves"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"In this kind of automaton, the transition function is additionally defined on the empty string ε.","segments":[{"text":"In this kind of automaton, the transition function is additionally defined on the empty string ε."}]},"unresolved":null},{"absence":null,"basis":"73bc1620dd81b0f8fe60b634bcc1d73682c0dcfea172a6f81050ef29fe4c9a7e","coverage":null,"id":"enwiki-653406-1366106761::In-text #39bdec98","item":"In-text #39bdec98","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA","end_line":48,"library":"mathlib","line":40,"location_key":"73bc1620dd81b0f8fe60b634bcc1d73682c0dcfea172a6f81050ef29fe4c9a7e","module":"Mathlib.Computability.EpsilonNFA","note":"The documentation of the structure itself calls a move taken on the absent symbol an epsilon-transition, so the library names the notion the passage names.","pair_key":"e4b516d49b9df1864622ccea3546cb4f41fcbae1eece9f12012f95d78d3f2172","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"structure εNFA : Type u → Type v → Type (max u v)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"aa87b614135f4b08c6922d8e9914f74eb91a2cb132293fc420a4901e637869c9","prominence":"supporting","quote":{"exact":"A transition without consuming an input symbol is called an ε-transition and"},"quote_capped":true,"section":["NFA with ε-moves"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"A transition without consuming an input symbol is called an ε-transition and is represented in state diagrams by an arrow labeled \"ε\".","segments":[{"text":"A transition without consuming an input symbol is called an ε-transition and is represented in state diagrams by an arrow labeled \"ε\"."}]},"unresolved":null},{"absence":null,"basis":"50b67808c5ff562006dbada41decd4c312cff89c399213a2bb9e314ca57a5f09","coverage":null,"id":"enwiki-653406-1366106761::In-text #158ac183","item":"In-text #158ac183","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA","end_line":48,"library":"mathlib","line":40,"location_key":"50b67808c5ff562006dbada41decd4c312cff89c399213a2bb9e314ca57a5f09","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib bundles the same five components as type parameters and fields, except that the start data is a set of states and neither the states nor the alphabet are required to be finite.","pair_key":"381c95a7566e2f70b89f8e2dec608a1695b468d4f0aa5ae6e985b422ffad799f","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"structure εNFA : Type u → Type v → Type (max u v)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"c651765264a67a07d495a9fcd7636d22af3c89431d47b0e71cea0af02a3b0ddc","prominence":"central","quote":{"exact":"a finite set of states Q {\\displaystyle Q} a finite set of"},"quote_capped":true,"section":["NFA with ε-moves","Formal definition"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"An NFA-ε is represented formally by a 5-tuple, ( Q , Σ , δ , q 0 , F ) {\\displaystyle (Q,\\Sigma ,\\delta ,q_{0},F)} , consisting of ","lead_in":true,"segments":[{"text":"An NFA-ε is represented formally by a 5-tuple, "},{"tex":"(Q,\\Sigma ,\\delta ,q_{0},F)"},{"text":" , consisting of "}]},"layer":"a finite set of states Q {\\displaystyle Q} a finite set of input symbols called the alphabet Σ {\\displaystyle \\Sigma } a transition function δ : Q × ( Σ ∪ { ε } ) → P ( Q ) {\\displaystyle \\delta :Q\\times (\\Sigma \\cup \\{\\varepsilon \\})\\rightarrow {\\mathcal {P}}(Q)} an initial (or start) state q 0 ∈ Q {\\displaystyle q_{0}\\in Q} a set of states F {\\displaystyle F} distinguished as accepting (or final) states F ⊆ Q {\\displaystyle F\\subseteq Q} .","segments":[{"text":"a finite set of states "},{"tex":"Q"},{"text":" a finite set of input symbols called the alphabet "},{"tex":"\\Sigma"},{"text":" a transition function "},{"tex":"\\delta :Q\\times (\\Sigma \\cup \\{\\varepsilon \\})\\rightarrow {\\mathcal {P}}(Q)"},{"text":" an initial (or start) state "},{"tex":"q_{0}\\in Q"},{"text":" a set of states "},{"tex":"F"},{"text":" distinguished as accepting (or final) states "},{"tex":"F\\subseteq Q"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"19de5e21d52e63a311c95ff3800898774f9b6db9f364ae1e4e60305663b7dacc","coverage":null,"id":"enwiki-653406-1366106761::In-text #837eca4f","item":"In-text #837eca4f","kind":"notation","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"Set.powerset","end_line":255,"library":"mathlib","line":255,"location_key":"19de5e21d52e63a311c95ff3800898774f9b6db9f364ae1e4e60305663b7dacc","module":"Mathlib.Data.Set.Defs","note":"Mathlib writes this operator with a script-P and defines it for an arbitrary set inside an arbitrary type.","pair_key":"36e6c127acb4d802228834b4fa7e9646b688723f60b9b147a2aaa04af8d869c3","path":"Mathlib/Data/Set/Defs.lean","proof_status":"definition","rank":1,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def Set.powerset {α : Type u} : Set α → Set (Set α)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"e30be04b1b15389770d883018dcb6876dfe362a92e69e0446c422ed32fd5919f","prominence":"supporting","quote":{"exact":"Here, P ( Q ) {\\displaystyle {\\mathcal {P}}(Q)} denotes the power set","suffix":" of Q {\\displaystyle Q} a"},"quote_capped":true,"section":["NFA with ε-moves","Formal definition"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Here, P ( Q ) {\\displaystyle {\\mathcal {P}}(Q)} denotes the power set of Q {\\displaystyle Q} and ε {\\displaystyle \\varepsilon } denotes empty string.","segments":[{"text":"Here, "},{"tex":"{\\mathcal {P}}(Q)"},{"text":" denotes the power set of "},{"tex":"Q"},{"text":" and "},{"tex":"\\varepsilon"},{"text":" denotes empty string."}]},"unresolved":null},{"absence":null,"basis":"2dcbdd494f6cd9675b134d809be07b99c0e3cacf73da12ba768ded05273f3355","coverage":null,"id":"enwiki-653406-1366106761::In-text #7196c93c","item":"In-text #7196c93c","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.εClosure","end_line":63,"library":"mathlib","line":63,"location_key":"2dcbdd494f6cd9675b134d809be07b99c0e3cacf73da12ba768ded05273f3355","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib defines the closure of a whole set of states; the article's operator on a single state is this one at the one-element set.","pair_key":"e5af81d8755458acc15871c55dde40b100d15fb0ccb56fecd1261ea82156a610","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.mem_εClosure_iff_exists_path","end_line":246,"library":"mathlib","line":225,"location_key":"499843b36442b6bab8ad31428cb5e0d929d48a422a81a0429e9732b831c13862","module":"Mathlib.Computability.EpsilonNFA","note":"The run is recorded as a list of repeated absent symbols, and the traversal predicate fixes its first and last state.","pair_key":"7f2a3d016604f75fea3042d3330ca41033d198bff7265735f5c0084ef7ff2719","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.mem_εClosure_iff_exists_path {α : Type u} {σ : Type v} (M : εNFA α σ) {s₁ s₂ : σ} : s₂ ∈ M.εClosure {s₁} ↔ ∃ n, M.IsPath s₁ s₂ (List.replicate n Option.none)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"2f2434ed1cd4f034fc548f66765f28e36e128937aafc54b6ada4d04a170b26dd","prominence":"central","quote":{"exact":"q 1 = q {\\displaystyle q_{1}=q} , q i + 1 ∈"},"quote_capped":true,"section":["NFA with ε-moves","ε-closure of a state or set of states"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":" E ( q ) {\\displaystyle E(q)} denote the set of states that are reachable from q {\\displaystyle q} by following ε-transitions in the transition function δ {\\displaystyle \\delta } , i.e., p ∈ E ( q ) {\\displaystyle p\\in E(q)} if there is a sequence of states q 1 , . . . , q k {\\displaystyle q_{1},...,q_{k}} such that ","lead_in":true,"segments":[{"text":" "},{"tex":"E(q)"},{"text":" denote the set of states that are reachable from "},{"tex":"q"},{"text":" by following ε-transitions in the transition function "},{"tex":"\\delta"},{"text":" , i.e., "},{"tex":"p\\in E(q)"},{"text":" if there is a sequence of states "},{"tex":"q_{1},...,q_{k}"},{"text":" such that "}],"trimmed":true},"layer":"q 1 = q {\\displaystyle q_{1}=q} , q i + 1 ∈ δ ( q i , ε ) {\\displaystyle q_{i+1}\\in \\delta (q_{i},\\varepsilon )} for each 1 ≤ i < k {\\displaystyle 1\\leq i<k} , and q k = p {\\displaystyle q_{k}=p} .","segments":[{"tex":"q_{1}=q"},{"text":" , "},{"tex":"q_{i+1}\\in \\delta (q_{i},\\varepsilon )"},{"text":" for each "},{"tex":"1\\leq i<k"},{"text":" , and "},{"tex":"q_{k}=p"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"63984d4598676a1ac50ae6c67088e04e45557a4caa01ae320307b5194396b802","coverage":null,"id":"enwiki-653406-1366106761::In-text #6ff3e790","item":"In-text #6ff3e790","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.εClosure","end_line":63,"library":"mathlib","line":63,"location_key":"63984d4598676a1ac50ae6c67088e04e45557a4caa01ae320307b5194396b802","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib carries this operator under the epsilon-closure name and documents it as reachability by a finite run of epsilon-moves.","pair_key":"463e1e645003a634cffcd6fbccec799a767cae76e10385773c75c10cb867a553","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"690ac3dcda048a2225ca5cf6a3da59134e8ab296b522a474c4bd6ff618fb3377","prominence":"central","quote":{"exact":"E ( q ) {\\displaystyle E(q)} is known as the epsilon closure,"},"quote_capped":true,"section":["NFA with ε-moves","ε-closure of a state or set of states"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"E ( q ) {\\displaystyle E(q)} is known as the epsilon closure, (also ε-closure) of q {\\displaystyle q} .","segments":[{"tex":"E(q)"},{"text":" is known as the epsilon closure, (also ε-closure) of "},{"tex":"q"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"c4e634784d03e4a77262fa1d567225ed9768f8726a128336c621c5e8af8e0ff6","coverage":null,"id":"enwiki-653406-1366106761::In-text #c835e20b","item":"In-text #c835e20b","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.εClosure","end_line":63,"library":"mathlib","line":63,"location_key":"c4e634784d03e4a77262fa1d567225ed9768f8726a128336c621c5e8af8e0ff6","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib's operator takes an arbitrary set of states and returns those reachable from one of its members by a finite run of epsilon-moves.","pair_key":"9aa305b6a47436e74f16d340080ae50f1b5617715e3e28ef3f120291fa41553d","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA.mem_εClosure_iff_exists","end_line":115,"library":"mathlib","line":104,"location_key":"824c631443c2299d4d513ff0c54f9fb7cb4a1181c146f2eebf37663e67c930b2","module":"Mathlib.Computability.EpsilonNFA","note":"The library writes the union over the members of the set elementwise rather than as an equality of two sets.","pair_key":"10994db2daa62ecc6c5ac6ca719260c7104ed6e465a4c2f30085223da3de2426","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.mem_εClosure_iff_exists {α : Type u} {σ : Type v} (M : εNFA α σ) {S : Set σ} {s : σ} : s ∈ M.εClosure S ↔ ∃ t ∈ S, s ∈ M.εClosure {t}"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"b37d9f9de5b42a6a43b4009b731db4f923cca817d646cb5ad4eadba00539d467","prominence":"supporting","quote":{"exact":"The ε-closure of a set P {\\displaystyle P} of states of an"},"quote_capped":true,"section":["NFA with ε-moves","ε-closure of a state or set of states"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The ε-closure of a set P {\\displaystyle P} of states of an NFA is defined as the set of states reachable from any state in P {\\displaystyle P} following ε-transitions.","segments":[{"text":"The ε-closure of a set "},{"tex":"P"},{"text":" of states of an NFA is defined as the set of states reachable from any state in "},{"tex":"P"},{"text":" following ε-transitions."}]},"unresolved":null},{"absence":null,"basis":"4058eda6d50d28f9948a32a3388f2b75311e2f6172aad7b1d5e4d13d422cf632","coverage":null,"id":"enwiki-653406-1366106761::In-text #58d21af5","item":"In-text #58d21af5","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.εClosure","end_line":63,"library":"mathlib","line":63,"location_key":"4058eda6d50d28f9948a32a3388f2b75311e2f6172aad7b1d5e4d13d422cf632","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib lets the state type be infinite, of which the article's finite Q is one case, and marks an ε-transition by the label none instead of the letter ε.","pair_key":"0d309b3b7fed49396cf1ebf0e86127cbdf3d3a754111dc54a57c6c2d212ba092","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.εClosure {α : Type u} {σ : Type v} : εNFA α σ → Set σ → Set σ"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.mem_εClosure_iff_exists","end_line":115,"library":"mathlib","line":104,"location_key":"6c9a4534a1b4e7839df2ec3a57e510c4328be6049d96ba3845ef3d910752b49b","module":"Mathlib.Computability.EpsilonNFA","note":"The equality of the two sets is phrased as a membership equivalence, and the closure of a one-element set plays the role of the article's closure of a single state.","pair_key":"5ce5a276b0d5e8f9157de7fe153fae92220dde7883ad0e89a6c8a90f54d07f0b","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.mem_εClosure_iff_exists {α : Type u} {σ : Type v} (M : εNFA α σ) {S : Set σ} {s : σ} : s ∈ M.εClosure S ↔ ∃ t ∈ S, s ∈ M.εClosure {t}"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"5805c20539add22dac0f52daa89574c07e24c64b0ba93c934c91f76e47d304c0","prominence":"supporting","quote":{"exact":"Formally, for P ⊆ Q {\\displaystyle P\\subseteq Q} , define E ("},"quote_capped":true,"section":["NFA with ε-moves","ε-closure of a state or set of states"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Formally, for P ⊆ Q {\\displaystyle P\\subseteq Q} , define E ( P ) = ⋃ q ∈ P E ( q ) {\\displaystyle E(P)=\\bigcup \\limits _{q\\in P}E(q)} .","segments":[{"text":"Formally, for "},{"tex":"P\\subseteq Q"},{"text":" , define "},{"tex":"E(P)=\\bigcup \\limits _{q\\in P}E(q)"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"2e1e40065da4bb8c2d9bc79bc2b6476685977cec3afda677fe7857a6c6d8411e","coverage":null,"id":"enwiki-653406-1366106761::In-text #d6cd45b9","item":"In-text #d6cd45b9","kind":"notation","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.evalFrom","end_line":136,"library":"mathlib","line":135,"location_key":"2e1e40065da4bb8c2d9bc79bc2b6476685977cec3afda677fe7857a6c6d8411e","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib starts the computation from a set of states rather than one state and allows infinitely many states, and strings are lists of alphabet letters.","pair_key":"e76ed23fabd0bf5373cbfab13df8cfff73658c594092777c8e573fbfaa257861","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.evalFrom {α : Type u} {σ : Type v} : εNFA α σ → Set σ → List α → Set σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"8c7a1d6f0c2d3304c4b0e6a8431a88478ff9dc3069e85695d6c082845b2481f6","prominence":"supporting","quote":{"exact":"Informally, δ ∗ ( q , w ) {\\displaystyle \\delta ^{*}(q,w)} denotes"},"quote_capped":true,"section":["NFA with ε-moves","Extended transition function"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" The function δ ∗ : Q × Σ ∗ → P ( Q ) {\\displaystyle \\delta ^{*}:Q\\times \\Sigma ^{*}\\rightarrow {\\mathcal {P}}(Q)} can be defined recursively as follows.","segments":[{"text":" The function "},{"tex":"\\delta ^{*}:Q\\times \\Sigma ^{*}\\rightarrow {\\mathcal {P}}(Q)"},{"text":" can be defined recursively as follows."}]},"layer":"Informally, δ ∗ ( q , w ) {\\displaystyle \\delta ^{*}(q,w)} denotes the set of all states the automaton may have reached when starting in state q ∈ Q {\\displaystyle q\\in Q} and reading the string w ∈ Σ ∗ . {\\displaystyle w\\in \\Sigma ^{*}.}","segments":[{"text":"Informally, "},{"tex":"\\delta ^{*}(q,w)"},{"text":" denotes the set of all states the automaton may have reached when starting in state "},{"tex":"q\\in Q"},{"text":" and reading the string "},{"tex":"w\\in \\Sigma ^{*}."}]},"unresolved":null},{"absence":null,"basis":"5ccf03f1a18c6c4755fed8c8ec8ed3c84b10f2d91a59bc99672e82e72887c8c3","coverage":null,"id":"enwiki-653406-1366106761::In-text #79d12e2e","item":"In-text #79d12e2e","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.evalFrom_nil","end_line":140,"library":"mathlib","line":139,"location_key":"5ccf03f1a18c6c4755fed8c8ec8ed3c84b10f2d91a59bc99672e82e72887c8c3","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib states the base case for a whole set of starting states, and the empty string is the empty list of letters.","pair_key":"458660dac0c61c204afc3f3516d3b356949d5c84f8d090595e7aeab4bf0ca3fd","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.evalFrom_nil {α : Type u} {σ : Type v} (M : εNFA α σ) (S : Set σ) : M.evalFrom S [] = M.εClosure S"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"c7839f26bb7ca12b48f440e0f6bc5421fc4b9e7276b8f779822d9d08a441ef4a","prominence":"central","quote":{"exact":"δ ∗ ( q , ε ) = E ( q )"},"quote_capped":true,"section":["NFA with ε-moves","Extended transition function"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"δ ∗ ( q , ε ) = E ( q ) {\\displaystyle \\delta ^{*}(q,\\varepsilon )=E(q)} , for each state q ∈ Q , {\\displaystyle q\\in Q,} and where E {\\displaystyle E} denotes the epsilon closure;","segments":[{"tex":"\\delta ^{*}(q,\\varepsilon )=E(q)"},{"text":" , for each state "},{"tex":"q\\in Q,"},{"text":" and where "},{"tex":"E"},{"text":" denotes the epsilon closure;"}]},"unresolved":null},{"absence":null,"basis":"499176ee803ed7c93d390ddd4dd19ffc084b08f60197951c359f8b1505e84f1c","coverage":null,"id":"enwiki-653406-1366106761::In-text #ffdfb67b","item":"In-text #ffdfb67b","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.evalFrom_append_singleton","end_line":149,"library":"mathlib","line":147,"location_key":"499176ee803ed7c93d390ddd4dd19ffc084b08f60197951c359f8b1505e84f1c","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib writes the union through its one-letter step operation on sets and encodes reading the letter a as the labelled option some a.","pair_key":"0a1e8c476e7db640ae86ca5cb340a3ded1746083bcd65fe141597a5592bec7de","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.evalFrom_append_singleton {α : Type u} {σ : Type v} (M : εNFA α σ) (S : Set σ) (x : List α) (a : α) : M.evalFrom S (x ++ [a]) = M.stepSet (M.evalFrom S x) a"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.stepSet","end_line":119,"library":"mathlib","line":118,"location_key":"ba4e3e67744c229e331302695602a8cdebbb722bcaa5a20d2dbb0e9e05576f60","module":"Mathlib.Computability.EpsilonNFA","note":"This is the operation whose definition supplies the union of ε-closures appearing on the right of the passage's equation, but on its own it says nothing about evaluating a string.","pair_key":"12dedac51ff55673e6a242356f89feb29b04187bf9dee03c48f959f2174a0175","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.stepSet {α : Type u} {σ : Type v} : εNFA α σ → Set σ → α → Set σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"f3c714dcf4367323669fdb205731a3225c633278ff3f025d6974e1e0f1c74e98","prominence":"central","quote":{"exact":"δ ∗ ( q , w a ) = ⋃ r ∈"},"quote_capped":true,"section":["NFA with ε-moves","Extended transition function"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"Informally: Reading the empty string may drive the automaton from state q {\\displaystyle q} to any state of the epsilon closure of q . {\\displaystyle q.} ","lead_in":true,"segments":[{"text":"Informally: Reading the empty string may drive the automaton from state "},{"tex":"q"},{"text":" to any state of the epsilon closure of "},{"tex":"q."},{"text":" "}]},"layer":"δ ∗ ( q , w a ) = ⋃ r ∈ δ ∗ ( q , w ) E ( δ ( r , a ) ) , {\\textstyle \\delta ^{*}(q,wa)=\\bigcup _{r\\in \\delta ^{*}(q,w)}E(\\delta (r,a)),} for each state q ∈ Q , {\\displaystyle q\\in Q,} each string w ∈ Σ ∗ {\\displaystyle w\\in \\Sigma ^{*}} and each symbol a ∈ Σ . {\\displaystyle a\\in \\Sigma .}","segments":[{"tex":"\\textstyle \\delta ^{*}(q,wa)=\\bigcup _{r\\in \\delta ^{*}(q,w)}E(\\delta (r,a)),"},{"text":" for each state "},{"tex":"q\\in Q,"},{"text":" each string "},{"tex":"w\\in \\Sigma ^{*}"},{"text":" and each symbol "},{"tex":"a\\in \\Sigma ."}]},"unresolved":null},{"absence":null,"basis":"aea3ef9cb6f41741219fc3a3893c9b1142e6270e50a2f399bb816c4181f31d9d","coverage":null,"id":"enwiki-653406-1366106761::In-text #fd951c76","item":"In-text #fd951c76","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.accepts","end_line":184,"library":"mathlib","line":183,"location_key":"aea3ef9cb6f41741219fc3a3893c9b1142e6270e50a2f399bb816c4181f31d9d","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib collects the accepted inputs into a language of lists and lets the automaton carry a set of initial states; asking for an accepting state in the reached set is the same as asking that the reached set meet the accepting ones.","pair_key":"58d27555fa2887adb79a7e659bcc1f18b6ef02dec380a31bb642339cb0e552ba","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.accepts {α : Type u} {σ : Type v} : εNFA α σ → Language α"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"375fdcdb0a51b90d9f025260f1d1d5d700e398dd5d183b6181705552533b548c","prominence":"central","quote":{"exact":"The automaton is said to accept a string w {\\displaystyle w} if"},"quote_capped":true,"section":["NFA with ε-moves","Extended transition function"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The automaton is said to accept a string w {\\displaystyle w} if δ ∗ ( q 0 , w ) ∩ F ≠ ∅ , {\\displaystyle \\delta ^{*}(q_{0},w)\\cap F\\neq \\emptyset ,} that is, if reading w {\\displaystyle w} may drive the automaton from its start state q 0 {\\displaystyle q_{0}} to some accepting state in F . {\\displaystyle F.}","segments":[{"text":"The automaton is said to accept a string "},{"tex":"w"},{"text":" if "},{"tex":"\\delta ^{*}(q_{0},w)\\cap F\\neq \\emptyset ,"},{"text":" that is, if reading "},{"tex":"w"},{"text":" may drive the automaton from its start state "},{"tex":"q_{0}"},{"text":" to some accepting state in "},{"tex":"F."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"d1a3502277e126785c8435da1576de5d6cc057a0122fda59be9e71a9c361eb3d"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #8256cf81","item":"In-text #8256cf81","kind":"example","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"6e0281f423b78c2bf941b8b4f3f14191bff33c9d4dd969bd8d4c3737ed5ee1ff","prominence":"supporting","quote":{"exact":"Let M {\\displaystyle M} be a NFA-ε, with a binary alphabet, that"},"quote_capped":true,"section":["NFA with ε-moves","Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Let M {\\displaystyle M} be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s.","segments":[{"text":"Let "},{"tex":"M"},{"text":" be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s."}]},"unresolved":null},{"absence":null,"basis":"c33fc5f8cb110d409e8f077cb2ef4687a7a8d6ddb94cceefa01ee95b2ba65007","coverage":null,"id":"enwiki-653406-1366106761::In-text #6c114d8a","item":"In-text #6c114d8a","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"Even.zero","end_line":104,"library":"mathlib","line":104,"location_key":"c33fc5f8cb110d409e8f077cb2ef4687a7a8d6ddb94cceefa01ee95b2ba65007","module":"Mathlib.Algebra.Group.Even","note":"Mathlib states this for any type with addition and a zero, of which the counts of occurrences are one case, and being even there means being the sum of something with itself.","pair_key":"e6b2cc752f9f2e08ac5e59ecd438ae7e0143955a8c2a81748b7eef84f50a97fa","path":"Mathlib/Algebra/Group/Even.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem Even.zero {α : Type*} [AddZeroClass α] : Even 0"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"b9fe9702804b3af843c1f1e5a64fef6df8a5f28e93dd6ea8f49df2f35c398b34","prominence":"supporting","quote":{"exact":"Note that 0 occurrences is an even number of occurrences as well."},"quote_capped":false,"section":["NFA with ε-moves","Example"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Note that 0 occurrences is an even number of occurrences as well.","segments":[{"text":"Note that 0 occurrences is an even number of occurrences as well."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":3,"sha256":"97a8cd77ce9c675362a615008f4e835d96f009f6ff042195901ce235e602b58d"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #522b085f","item":"In-text #522b085f","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"25022a1c4b70d5c8b696282993a7d5cceabc447a9c9ef52d71e1035ce0825219","prominence":"supporting","quote":{"exact":"M {\\displaystyle M} can be viewed as the union of two DFAs:"},"quote_capped":true,"section":["NFA with ε-moves","Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"M {\\displaystyle M} can be viewed as the union of two DFAs: one with states { S 1 , S 2 } {\\displaystyle \\{S_{1},S_{2}\\}} and the other with states { S 3 , S 4 } {\\displaystyle \\{S_{3},S_{4}\\}} .","segments":[{"tex":"M"},{"text":" can be viewed as the union of two DFAs: one with states "},{"tex":"\\{S_{1},S_{2}\\}"},{"text":" and the other with states "},{"tex":"\\{S_{3},S_{4}\\}"},{"text":" ."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":5,"sha256":"219a34231fb431e02738aedc019c7336c85a372db9358b4b7fc7bda610fafaee"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #515dc09f","item":"In-text #515dc09f","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"5b269384eabbb5452dd2d2fde92e33f9fed94763ef74e8d1f6fe3276a8911c23","prominence":"supporting","quote":{"exact":"The language of M {\\displaystyle M} can be described by the regular"},"quote_capped":true,"section":["NFA with ε-moves","Example"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The language of M {\\displaystyle M} can be described by the regular language given by this regular expression ( 1 ∗ 01 ∗ 01 ∗ ) ∗ ∪ ( 0 ∗ 10 ∗ 10 ∗ ) ∗ {\\displaystyle (1^{*}01^{*}01^{*})^{*}\\cup (0^{*}10^{*}10^{*})^{*}} .","segments":[{"text":"The language of "},{"tex":"M"},{"text":" can be described by the regular language given by this regular expression "},{"tex":"(1^{*}01^{*}01^{*})^{*}\\cup (0^{*}10^{*}10^{*})^{*}"},{"text":" ."}]},"unresolved":null},{"absence":null,"basis":"e01d6a0050fe536a581b7e7ecb7f35551da2ee0830ebb7c031e6991ec748445d","coverage":null,"id":"enwiki-653406-1366106761::In-text #e36bcdea","item":"In-text #e36bcdea","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA.toNFA_correct","end_line":313,"library":"mathlib","line":312,"location_key":"e01d6a0050fe536a581b7e7ecb7f35551da2ee0830ebb7c031e6991ec748445d","module":"Mathlib.Computability.EpsilonNFA","note":"The ε-free automaton the lemma produces is Lean's own conversion, so the machine it exhibits need not be the one a reader would draw by hand.","pair_key":"a928ecdb6c6f28b08a490f24417364bf49b05f4ae48ce0a10183170125e39de0","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.toNFA","end_line":304,"library":"mathlib","line":301,"location_key":"986fc327f904faff1a0799a9b32f8a5675c794d23f2268dd13031ad2d536c0f7","module":"Mathlib.Computability.EpsilonNFA","note":"This is the conversion that removes the ε-steps; on its own it asserts nothing about the language of the machine it builds.","pair_key":"890ea2b30a3bc0e21c23af72d59b0ce196d96c51d8fc7ae2e725bf4d2c677c9e","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.toNFA {α : Type u} {σ : Type v} : εNFA α σ → NFA α σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"8158f948e75baaae86a00bdd83f495814698149e3c1e11fa4d3da49c3aa27190","prominence":"supporting","quote":{"exact":"We define M {\\displaystyle M} using ε-moves but M {\\displaystyle M} can"},"quote_capped":true,"section":["NFA with ε-moves","Example"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"We define M {\\displaystyle M} using ε-moves but M {\\displaystyle M} can be defined without using ε-moves.","segments":[{"text":"We define "},{"tex":"M"},{"text":" using ε-moves but "},{"tex":"M"},{"text":" can be defined without using ε-moves."}]},"unresolved":null},{"absence":null,"basis":"aa28077a159a21617746e6e13df32165c74d0b9f40034740685291751d375313","coverage":null,"id":"enwiki-653406-1366106761::In-text #87171aed","item":"In-text #87171aed","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toεNFA_correct","end_line":352,"library":"mathlib","line":350,"location_key":"aa28077a159a21617746e6e13df32165c74d0b9f40034740685291751d375313","module":"Mathlib.Computability.EpsilonNFA","note":"Lean keeps the two kinds of automaton as distinct types, so the inclusion is encoded as a conversion that reuses the states, the start and accept sets and the transitions and adds no ε-step, and the lemma records that the accepted language is unchanged.","pair_key":"f5c3d48a751263e25338b43b535e64ad113d4c3a9fb8acb3858fc5eba723e13a","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"closeMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toεNFA_correct {α : Type u} {σ : Type v} (M : NFA α σ) : M.toεNFA.accepts = M.accepts"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toεNFA","end_line":330,"library":"mathlib","line":327,"location_key":"d043fcf2f8b0a5e329672735ede54357844122670dade2af6cf95b6a11f31253","module":"Mathlib.Computability.EpsilonNFA","note":"The conversion by itself, documented as reusing the start and accept states and the transitions, but stating nothing about languages.","pair_key":"3a044503fc28a09a340bb6481c569a24e8e95c7eccc57b130ec9f3129268f16d","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.toεNFA {α : Type u} {σ : Type v} : NFA α σ → εNFA α σ"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"321f2915100edf6341f95be0bd39416d5acff5d84b9326b1f6bb0469c26b1fbb","prominence":"supporting","quote":{"exact":"To show NFA-ε is equivalent to NFA, first note that NFA is"},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":", so it remains to show for every NFA-ε, there exists an equivalent NFA.","segments":[{"text":", so it remains to show for every NFA-ε, there exists an equivalent NFA."}]},"layer":"To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε","segments":[{"text":"To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε"}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":3,"queries":3,"sha256":"49224640f750f292a879eb520dec9cf7b07c54923e54d7c580ba6f499934becc"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #ec23ca28","item":"In-text #ec23ca28","kind":"construction","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA.toNFA","end_line":304,"library":"mathlib","line":301,"location_key":"2e90011fdbd2dc63d47db420ddfe776006dd488dad3d6aa907c99482556b3e2a","module":"Mathlib.Computability.EpsilonNFA","note":"Lean's conversion builds an ε-free automaton from one with ε-moves, but not by the passage's two equations: because its automata carry a set of start states it closes that set under ε-steps and leaves the accepting states alone, instead of adding the start state to them.","pair_key":"06ecfae4dcf07d371e137f1732e26038396ee1ab12c02a6d2270ece75906a536","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"definition","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def εNFA.toNFA {α : Type u} {σ : Type v} : εNFA α σ → NFA α σ"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"34f52d73fa68080d2bef68fe3184c7f1c8364b35e16bcd9ce5a7fc0102fc33b8","prominence":"central","quote":{"exact":"Given an NFA with epsilon moves M = ( Q , Σ"},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Given an NFA with epsilon moves M = ( Q , Σ , δ , q 0 , F ) , {\\displaystyle M=(Q,\\Sigma ,\\delta ,q_{0},F),} define an NFA M ′ = ( Q , Σ , δ ′ , q 0 , F ′ ) , {\\displaystyle M'=(Q,\\Sigma ,\\delta ',q_{0},F'),} where F ′ = { F ∪ { q 0 } if E ( q 0 ) ∩ F ≠ { } F otherwise {\\displaystyle F'={\\begin{cases}F\\cup \\{q_{0}\\}&{\\text{ if }}E(q_{0})\\cap F\\neq \\{\\}\\\\F&{\\text{ otherwise }}\\\\\\end{cases}}} and δ ′ ( q , a ) = δ ∗ ( q , a ) {\\displaystyle \\delta '(q,a)=\\delta ^{*}(q,a)} for each state q ∈ Q {\\displaystyle q\\in Q} and each symbol a ∈ Σ , {\\displaystyle a\\in \\Sigma ,} using the extended transition function δ ∗ {\\displaystyle \\delta ^{*}} defined above.","segments":[{"text":"Given an NFA with epsilon moves "},{"tex":"M=(Q,\\Sigma ,\\delta ,q_{0},F),"},{"text":" define an NFA "},{"tex":"M'=(Q,\\Sigma ,\\delta ',q_{0},F'),"},{"text":" where "},{"tex":"F'={\\begin{cases}F\\cup \\{q_{0}\\}&{\\text{ if }}E(q_{0})\\cap F\\neq \\{\\}\\\\F&{\\text{ otherwise }}\\\\\\end{cases}}"},{"text":" and "},{"tex":"\\delta '(q,a)=\\delta ^{*}(q,a)"},{"text":" for each state "},{"tex":"q\\in Q"},{"text":" and each symbol "},{"tex":"a\\in \\Sigma ,"},{"text":" using the extended transition function "},{"tex":"\\delta ^{*}"},{"text":" defined above."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":3,"sha256":"e913751997e7da96553262eb9c8cdc2a9321f68b1e0bb90a0e71290908cb414f"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #a401c727","item":"In-text #a401c727","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"9ec371ee9ddfcd3fa2cede2165df0cb8e633aeecbb847b19b5c8976adf2d2451","prominence":"supporting","quote":{"exact":"By construction, M ′ {\\displaystyle M'} has no ε-transitions."},"quote_capped":false,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"By construction, M ′ {\\displaystyle M'} has no ε-transitions.","segments":[{"text":"By construction, "},{"tex":"M'"},{"text":" has no ε-transitions."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":3,"sha256":"f23c0b017883f2ed3ba81f406d6086856674c68fc4e66152da9a6e65b511a890"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #56a12efa","item":"In-text #56a12efa","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA.toNFA_evalFrom_match","end_line":309,"library":"mathlib","line":307,"location_key":"a88bc79679975de9535c6211547e5ac1bf3f28b426ba9e1f9d83fed1edd9c44d","module":"Mathlib.Computability.EpsilonNFA","note":"It matches the evaluations of Lean's converted machine and the original one, but only after the ε-closure is applied to the start set, and for a conversion whose transitions differ from the passage's.","pair_key":"951f25c39ded54470b45f623014231092490de4b34cb939588fb6cd411dc399b","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.toNFA_evalFrom_match {α : Type u} {σ : Type v} (M : εNFA α σ) (start : Set σ) : M.toNFA.evalFrom (M.εClosure start) = M.evalFrom start"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"866be2fd092649ec45f1f2ff58bca176e7f86b636b4917cb48ebd85a26442796","prominence":"supporting","quote":{"exact":"One can prove that δ ′ ∗ ( q 0 , w"},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"One can prove that δ ′ ∗ ( q 0 , w ) = δ ∗ ( q 0 , w ) {\\displaystyle \\delta '^{*}(q_{0},w)=\\delta ^{*}(q_{0},w)} for each string w ≠ ε {\\displaystyle w\\neq \\varepsilon } , by induction on the length of w . {\\displaystyle w.}","segments":[{"text":"One can prove that "},{"tex":"\\delta '^{*}(q_{0},w)=\\delta ^{*}(q_{0},w)"},{"text":" for each string "},{"tex":"w\\neq \\varepsilon"},{"text":" , by induction on the length of "},{"tex":"w."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":3,"queries":3,"sha256":"23be13ea74a50a11c1e2c10ceb37221709f72a776c9aa59739cf2b0ecfd269bd"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #2b75f1f1","item":"In-text #2b75f1f1","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA.toNFA_correct","end_line":313,"library":"mathlib","line":312,"location_key":"1853550c8ff68ca57900ac748eb7e6d55d74e5893a5b6ec2804de29a4b46b44f","module":"Mathlib.Computability.EpsilonNFA","note":"The universe does prove that removing ε-steps preserves the accepted language, but for its own conversion, whose start set is ε-closed and whose accepting states are untouched, so it is a statement about another machine than the one the passage built.","pair_key":"7251b257c2e8d8622f60e30ef7e4afd4ee7ef60de4462f74477b7d5e503be8b4","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"c6d61bd3bb3d12cbaaeb8be5079939a6ebde74d3d0c9683275d8123f73b1b787","prominence":"central","quote":{"exact":"Based on this, one can show that δ ′ ∗ ( q"},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Based on this, one can show that δ ′ ∗ ( q 0 , w ) ∩ F ′ ≠ { } {\\displaystyle \\delta '^{*}(q_{0},w)\\cap F'\\neq \\{\\}} if, and only if, δ ∗ ( q 0 , w ) ∩ F ≠ { } , {\\displaystyle \\delta ^{*}(q_{0},w)\\cap F\\neq \\{\\},} for each string w ∈ Σ ∗ : {\\displaystyle w\\in \\Sigma ^{*}:}","segments":[{"text":"Based on this, one can show that "},{"tex":"\\delta '^{*}(q_{0},w)\\cap F'\\neq \\{\\}"},{"text":" if, and only if, "},{"tex":"\\delta ^{*}(q_{0},w)\\cap F\\neq \\{\\},"},{"text":" for each string "},{"tex":"w\\in \\Sigma ^{*}:"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":3,"sha256":"c2ce124a9751886bafb44266b862d42e61368d0ed33c36da717230a7cb5a08dd"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #a5345929","item":"In-text #a5345929","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"296f5993102e49e76b2962a36ab3b2a6c62904d082db7c35f4a8195c93fdd06e","prominence":"supporting","quote":{"exact":"From δ ′ ∗ ( q 0 , w ) = δ"},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" we still have to show the \" ⇒ {\\displaystyle \\Rightarrow } \" direction.","segments":[{"text":" we still have to show the \" "},{"tex":"\\Rightarrow"},{"text":" \" direction."}]},"before":{"layer":"Otherwise, let w = v a {\\displaystyle w=va} with v ∈ Σ ∗ {\\displaystyle v\\in \\Sigma ^{*}} and a ∈ Σ . {\\displaystyle a\\in \\Sigma .} ","lead_in":true,"segments":[{"text":"Otherwise, let "},{"tex":"w=va"},{"text":" with "},{"tex":"v\\in \\Sigma ^{*}"},{"text":" and "},{"tex":"a\\in \\Sigma ."},{"text":" "}]},"layer":"From δ ′ ∗ ( q 0 , w ) = δ ∗ ( q 0 , w ) {\\displaystyle \\delta '^{*}(q_{0},w)=\\delta ^{*}(q_{0},w)} and F ⊆ F ′ , {\\displaystyle F\\subseteq F',} we have δ ′ ∗ ( q 0 , w ) ∩ F ′ ≠ { } ⇐ δ ∗ ( q 0 , w ) ∩ F ≠ { } ; {\\displaystyle \\delta '^{*}(q_{0},w)\\cap F'\\neq \\{\\}\\;\\Leftarrow \\;\\delta ^{*}(q_{0},w)\\cap F\\neq \\{\\};}","segments":[{"text":"From "},{"tex":"\\delta '^{*}(q_{0},w)=\\delta ^{*}(q_{0},w)"},{"text":" and "},{"tex":"F\\subseteq F',"},{"text":" we have "},{"display":true,"tex":"\\delta '^{*}(q_{0},w)\\cap F'\\neq \\{\\}\\;\\Leftarrow \\;\\delta ^{*}(q_{0},w)\\cap F\\neq \\{\\};"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"4985b5fead19d732592d379eec882ba74d71fe0ffbd0c8ab056600888d5655c8"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #a70b6f0f","item":"In-text #a70b6f0f","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.toNFA_evalFrom_match","end_line":309,"library":"mathlib","line":307,"location_key":"9c8f122281c783cb63a83558d99ce5c565608a5de5bc61bdf0a03d6fce7006dd","module":"Mathlib.Computability.EpsilonNFA","note":"Mathlib converts an automaton with epsilon-moves by taking the epsilon closure of the start set and keeping the accepting set, so it never speaks of the article's enlarged accepting set.","pair_key":"20831d89800fe6770835292fdd39a6a873f766d838e0eb16d1a2ee8f970dbd23","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.toNFA_evalFrom_match {α : Type u} {σ : Type v} (M : εNFA α σ) (start : Set σ) : M.toNFA.evalFrom (M.εClosure start) = M.evalFrom start"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.toNFA_correct","end_line":313,"library":"mathlib","line":312,"location_key":"629b4d9e74a9f0e3a7a9e56956868bf8dec8e6ca23ce62858d37ee3cc12c5608","module":"Mathlib.Computability.EpsilonNFA","note":"This is the whole correctness statement of a different conversion, not the article's case analysis on where an accepting state of the new automaton came from.","pair_key":"83965facfcf6fbce6e749bfba69bea5b38fc81fce16e49bd60eb333c7d79f14c","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"3066621928b2c5a23a86b90a5f6714b992a8db4360182bdc34a3a26b5e7489c6","prominence":"supporting","quote":{"exact":"If δ ′ ∗ ( q 0 , w ) {\\displaystyle \\delta","prefix":"n. "},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"If δ ′ ∗ ( q 0 , w ) {\\displaystyle \\delta '^{*}(q_{0},w)} contains a state in F ′ ∖ { q 0 } , {\\displaystyle F'\\setminus \\{q_{0}\\},} then δ ∗ ( q 0 , w ) {\\displaystyle \\delta ^{*}(q_{0},w)} contains the same state, which lies in F {\\displaystyle F} .","segments":[{"text":"If "},{"tex":"\\delta '^{*}(q_{0},w)"},{"text":" contains a state in "},{"tex":"F'\\setminus \\{q_{0}\\},"},{"text":" then "},{"tex":"\\delta ^{*}(q_{0},w)"},{"text":" contains the same state, which lies in "},{"tex":"F"},{"text":" ."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"f15251ce4cdbb875e8e903bfc8330a1f0090bc57006e1e9e0b891a9e07bc540d"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #5b8b9ff6","item":"In-text #5b8b9ff6","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.subset_εClosure","end_line":65,"library":"mathlib","line":65,"location_key":"dd3219ffe8500ee8773d375c173bb23ae21b3531e89ad6eac458caa6daa1481a","module":"Mathlib.Computability.EpsilonNFA","note":"It only records that a set of states is contained in its own epsilon closure, which is a background fact rather than the passage's conditional claim.","pair_key":"bc15778879469547cbbb67649eaa5761d10441e42787289958913413fb21c4cf","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.subset_εClosure {α : Type u} {σ : Type v} (M : εNFA α σ) (S : Set σ) : S ⊆ M.εClosure S"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"bf91b34c25350fcbe28649c5c8d180b8d8bf2fa615a8a34794a5aa94f0e61a66","prominence":"supporting","quote":{"exact":"If δ ′ ∗ ( q 0 , w ) {\\displaystyle \\delta","prefix":" . "},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":" If δ ′ ∗ ( q 0 , w ) {\\displaystyle \\delta '^{*}(q_{0},w)} contains q 0 , {\\displaystyle q_{0},} and q 0 ∉ F , {\\displaystyle q_{0}\\not \\in F,} but q 0 ∈ F ′ , {\\displaystyle q_{0}\\in F',} then there exists a state in E ( q 0 ) ∩ F {\\displaystyle E(q_{0})\\cap F} , and the same state must be in δ ∗ ( q 0 , w ) = ⋃ r ∈ δ ∗ ( q , v ) E ( δ ( r , a ) ) . {\\textstyle \\delta ^{*}(q_{0},w)=\\bigcup _{r\\in \\delta ^{*}(q,v)}E(\\delta (r,a)).}","segments":[{"text":" If "},{"tex":"\\delta '^{*}(q_{0},w)"},{"text":" contains "},{"tex":"q_{0},"},{"text":" and "},{"tex":"q_{0}\\not \\in F,"},{"text":" but "},{"tex":"q_{0}\\in F',"},{"text":" then there exists a state in "},{"tex":"E(q_{0})\\cap F"},{"text":" , and the same state must be in "},{"tex":"\\textstyle \\delta ^{*}(q_{0},w)=\\bigcup _{r\\in \\delta ^{*}(q,v)}E(\\delta (r,a))."}],"trimmed":true},"layer":"If δ ′ ∗ ( q 0 , w ) {\\displaystyle \\delta '^{*}(q_{0},w)} contains q 0 , {\\displaystyle q_{0},} and q 0 ∈ F , {\\displaystyle q_{0}\\in F,} then δ ∗ ( q 0 , w ) {\\displaystyle \\delta ^{*}(q_{0},w)} also contains a state in F , {\\displaystyle F,} viz. q 0 . {\\displaystyle q_{0}.}","segments":[{"text":"If "},{"tex":"\\delta '^{*}(q_{0},w)"},{"text":" contains "},{"tex":"q_{0},"},{"text":" and "},{"tex":"q_{0}\\in F,"},{"text":" then "},{"tex":"\\delta ^{*}(q_{0},w)"},{"text":" also contains a state in "},{"tex":"F,"},{"text":" viz. "},{"tex":"q_{0}."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":3,"queries":3,"sha256":"1d198b10aee948df2e2a68105b190cd161f04b890e4e246d71cf252b8b51bed2"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #df0599a2","item":"In-text #df0599a2","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"εNFA.eval_nil","end_line":172,"library":"mathlib","line":171,"location_key":"4769b772b75776e7564fa7ed9d3a6a7187f8437353a1487354fc372a0d48db97","module":"Mathlib.Computability.EpsilonNFA","note":"It computes the set reached on the empty word as the epsilon closure of the start set, which is the object the first conjunct mentions but not the claim made about it.","pair_key":"414ea9c789d76ea56ba86df9dcabb10df0327011542ce0f05ebac7d90cf5f290","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.eval_nil {α : Type u} {σ : Type v} (M : εNFA α σ) : M.eval [] = M.εClosure M.start"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"ee807e1e23eeb31a2f3eeefa3a2409c521a01cf737b59cc5b056822557ec79a7","prominence":"supporting","quote":{"exact":"If δ ′ ∗ ( q 0 , w ) {\\displaystyle \\delta","prefix":"} "},"quote_capped":true,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"q 0 . {\\displaystyle q_{0}.} ","segments":[{"tex":"q_{0}."},{"text":" "}]},"layer":"If δ ′ ∗ ( q 0 , w ) {\\displaystyle \\delta '^{*}(q_{0},w)} contains q 0 , {\\displaystyle q_{0},} and q 0 ∉ F , {\\displaystyle q_{0}\\not \\in F,} but q 0 ∈ F ′ , {\\displaystyle q_{0}\\in F',} then there exists a state in E ( q 0 ) ∩ F {\\displaystyle E(q_{0})\\cap F} , and the same state must be in δ ∗ ( q 0 , w ) = ⋃ r ∈ δ ∗ ( q , v ) E ( δ ( r , a ) ) . {\\textstyle \\delta ^{*}(q_{0},w)=\\bigcup _{r\\in \\delta ^{*}(q,v)}E(\\delta (r,a)).}","segments":[{"text":"If "},{"tex":"\\delta '^{*}(q_{0},w)"},{"text":" contains "},{"tex":"q_{0},"},{"text":" and "},{"tex":"q_{0}\\not \\in F,"},{"text":" but "},{"tex":"q_{0}\\in F',"},{"text":" then there exists a state in "},{"tex":"E(q_{0})\\cap F"},{"text":" , and the same state must be in "},{"tex":"\\textstyle \\delta ^{*}(q_{0},w)=\\bigcup _{r\\in \\delta ^{*}(q,v)}E(\\delta (r,a))."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":0,"queries":3,"sha256":"57eb0efc7df6359333e57036915dacc303bfbfd40dc49157bd269507bb951a1b"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #3e0f5319","item":"In-text #3e0f5319","kind":"theorem","locations":[{"challenge":"downgraded","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"εNFA.toNFA_correct","end_line":313,"library":"mathlib","line":312,"location_key":"46faecb2f218cd45efe939e05585d925fbfb65e44b408414a37590eaa300655d","module":"Mathlib.Computability.EpsilonNFA","note":"The declaration lands in the epsilon-free model; the index ties that model to the deterministic one by its own pair of conversion theorems, which I read as two presentations of the recognizable languages rather than as a further hypothesis.","pair_key":"03f5e3174b3a8e5386f0266f5afeb50408499aa730a8e99457ff27a66ebb9053","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem εNFA.toNFA_correct {α : Type u} {σ : Type v} (M : εNFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false},{"challenge":"downgraded","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.toεNFA_correct","end_line":352,"library":"mathlib","line":350,"location_key":"b40461e2ed3e72303d4a2f84423ac87df2d98c496b419da16e31638749069d5b","module":"Mathlib.Computability.EpsilonNFA","note":"It supplies the easy inclusion of the equivalence, the one the article disposes of by calling the smaller model a special case of the larger.","pair_key":"37aaa5362a45527aca7c1764ee9939a397fcdeedcd8dc67b967e2f0da8a8e2f0","path":"Mathlib/Computability/EpsilonNFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toεNFA_correct {α : Type u} {σ : Type v} (M : NFA α σ) : M.toεNFA.accepts = M.accepts"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"71019ddbb9233649a6d1bc5e4abbcd1b23588f1e81e6d369a979fe68336eac4e","prominence":"central","quote":{"exact":"NFA-ε is also equivalent to DFA."},"quote_capped":false,"section":["NFA with ε-moves","Equivalence to NFA"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"Since NFA is equivalent to DFA, ","segments":[{"text":"Since NFA is equivalent to DFA, "}]},"layer":"NFA-ε is also equivalent to DFA.","segments":[{"text":"NFA-ε is also equivalent to DFA."}]},"unresolved":null},{"absence":null,"basis":"47726ec03bd582f24d11404112a3d5a97eb2fa19a121c4c7ac32bf1f32573e17","coverage":null,"id":"enwiki-653406-1366106761::In-text #a1778adf","item":"In-text #a1778adf","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA_correct","end_line":315,"library":"mathlib","line":312,"location_key":"47726ec03bd582f24d11404112a3d5a97eb2fa19a121c4c7ac32bf1f32573e17","module":"Mathlib.Computability.NFA","note":"Mathlib puts no finiteness demand on the state type, so the finiteness the regular-language predicate wants comes from the passage's own automaton.","pair_key":"4f66decac9aa45018db821718266e046dd44304616fcb75ddeb9e7b50d14da08","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA_correct","end_line":354,"library":"mathlib","line":348,"location_key":"1d8839b32b85f0ea096ad919c85171b982d4a9b8030f252554133716d6451479","module":"Mathlib.Computability.NFA","note":"The converted automaton keeps the state set, so the finiteness the passage expects of an automaton is preserved.","pair_key":"ce67faa1534001d78df553d699905c108d0d9468092899a6a9593d32a383ab3a","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"8cb7b9126e4dee51c507bdf9a4778399230bda37508deff69076c4c58e3df02e","prominence":"central","quote":{"exact":"They can also be used to prove that NFAs recognize exactly the"},"quote_capped":true,"section":["Closure properties"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"They can also be used to prove that NFAs recognize exactly the regular languages.","segments":[{"text":"They can also be used to prove that NFAs recognize exactly the regular languages."}]},"unresolved":null},{"absence":null,"basis":"203ab2bbfd7049e7270e27db534f06de9de9f8da1b1f3044d2cee4c395f6cd0f","coverage":null,"id":"enwiki-653406-1366106761::In-text #94a72f6c","item":"In-text #94a72f6c","kind":"theorem","locations":[{"challenge":"downgraded","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"Language.IsRegular.add","end_line":394,"library":"mathlib","line":390,"location_key":"203ab2bbfd7049e7270e27db534f06de9de9f8da1b1f3044d2cee4c395f6cd0f","module":"Mathlib.Computability.DFA","note":"Mathlib phrases the closure with its recognizability predicate, whose witness is a finite deterministic machine, and the index links that model to the nondeterministic one by its two conversion theorems; the sum of two languages is their union.","pair_key":"5387021dab4afe7c7ad2a878a40d561d1a21e84441e86032334d4ddef2a85420","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":1,"relation":"narrowMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem Language.IsRegular.add {T : Type u} {L1 L2 : Language T} : L1.IsRegular → L2.IsRegular → (L1 + L2).IsRegular"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"53b9fc7bb1e481117ed703719e04b8390c4900c3ea3e72d3a1507738cded8e42","prominence":"central","quote":{"exact":"Union (cf. picture); that is, if the language L1 is accepted by"},"quote_capped":true,"section":["Closure properties"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Union (cf. picture); that is, if the language L1 is accepted by some NFA A1 and L2 by some A2, then an NFA Au can be constructed that accepts the language L1∪L2.","segments":[{"text":"Union (cf. picture); that is, if the language L1 is accepted by some NFA A1 and L2 by some A2, then an NFA Au can be constructed that accepts the language L1∪L2."}]},"unresolved":null},{"absence":null,"basis":"bc4df89185c4950804428d87efcea0c992549fb27bfdec8b6b08233ce80fff75","coverage":null,"id":"enwiki-653406-1366106761::In-text #c330c410","item":"In-text #c330c410","kind":"theorem","locations":[{"challenge":"downgraded","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"Language.IsRegular.inf","end_line":401,"library":"mathlib","line":397,"location_key":"bc4df89185c4950804428d87efcea0c992549fb27bfdec8b6b08233ce80fff75","module":"Mathlib.Computability.DFA","note":"Mathlib phrases the closure with its recognizability predicate, whose witness is a finite deterministic machine, and the index links that model to the nondeterministic one by its two conversion theorems; the meet of two languages is their intersection.","pair_key":"cb48ccc03bdf6f30e18d55325d2543996ec1a6f68e1050765e6ce374035ac8ae","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":1,"relation":"narrowMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem Language.IsRegular.inf {T : Type u} {L1 L2 : Language T} : L1.IsRegular → L2.IsRegular → (L1 ⊓ L2).IsRegular"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"44a0aaec73a5602b4e8ef8d77903c81b80940e39b0a9857dbc84ac62b774d731","prominence":"central","quote":{"exact":"Intersection; similarly, from A1 and A2 an NFA Ai can be constructed"},"quote_capped":true,"section":["Closure properties"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Intersection; similarly, from A1 and A2 an NFA Ai can be constructed that accepts L1∩L2.","segments":[{"text":"Intersection; similarly, from A1 and A2 an NFA Ai can be constructed that accepts L1∩L2."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":4,"queries":4,"sha256":"bdb15dc55183eb2ee55576b8ddb5e9025e8ad367f40721ce5c99c54a5fbc1a5d"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #7ce89f9b","item":"In-text #7ce89f9b","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"RegularExpression.matches'_mul","end_line":120,"library":"mathlib","line":119,"location_key":"33d769b637e45ff8506962758578c89c13afae0c9412555cca753fa7e1a1a79d","module":"Mathlib.Computability.RegularExpressions","note":"It gives concatenation closure for the languages denoted by regular expressions, and this universe holds no theorem connecting that class to the automaton-recognizable one.","pair_key":"37d8590954240f99d7a0b194d8d6fe4c4024410cd97bede400172184fadf4e00","path":"Mathlib/Computability/RegularExpressions.lean","proof_status":"proved","rank":1,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem RegularExpression.matches'_mul {α : Type*} (P Q : RegularExpression α) : (P * Q).matches' = P.matches' * Q.matches'"},"statement":false}],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"4a8e11d7b800abae9b04966dacbafcc942177ecd88f753f250fcb3ecdec0b3cb","prominence":"central","quote":{"exact":"Concatenation"},"quote_capped":false,"section":["Closure properties"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Concatenation","segments":[{"text":"Concatenation"}]},"unresolved":null},{"absence":null,"basis":"c6d2b0a862c0351f0130d22a125babe1e2fb3b7742cebbe3bf35bb50f5c8925a","coverage":null,"id":"enwiki-653406-1366106761::In-text #ea259aef","item":"In-text #ea259aef","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"DFA.accepts_compl","end_line":288,"library":"mathlib","line":287,"location_key":"c6d2b0a862c0351f0130d22a125babe1e2fb3b7742cebbe3bf35bb50f5c8925a","module":"Mathlib.Computability.DFA","note":"Mathlib carries out the complementation only for deterministic machines, which are the deterministic cases of the article's A1, and its complement is taken inside the set of all strings over the alphabet.","pair_key":"ca60234ae1ce21a31ee285a4ebba1d42d3fda7914516d16ffcc90ac3ef43761f","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":1,"relation":"narrowMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.accepts_compl {α : Type u} {σ : Type v} (M : DFA α σ) : Mᶜ.accepts = M.acceptsᶜ"},"statement":false},{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"Language.IsRegular.compl","end_line":378,"library":"mathlib","line":376,"location_key":"ad7220b39e3fe4ee6b6444a2223eba460f8c7ad782eb5311b0f7f0432e0bd2a1","module":"Mathlib.Computability.DFA","note":"Closure under complement is stated for languages defined by a finite deterministic machine, so carrying it to the article's nondeterministic machines needs the subset construction in both directions.","pair_key":"15e7a6bf0a2aaefc1840a817b542311db87f9b101fd8851829760c6fd08951e2","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem Language.IsRegular.compl {T : Type u} {L : Language T} : L.IsRegular → Lᶜ.IsRegular"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"9c349a5dda4fa901e0f6a18d8d0a3823027fc8eae153be486859955d56d63483","prominence":"central","quote":{"exact":"Negation; similarly, from A1 an NFA An can be constructed that accepts"},"quote_capped":true,"section":["Closure properties"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"Concatenation ","lead_in":true,"segments":[{"text":"Concatenation "}]},"layer":"Negation; similarly, from A1 an NFA An can be constructed that accepts Σ*\\L1.","segments":[{"text":"Negation; similarly, from A1 an NFA An can be constructed that accepts Σ*\\L1."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":4,"queries":4,"sha256":"21c405dcec3a222618e1cfd166c2f07919221c6b3955c238d2315623a2d7894b"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #edb25e4e","item":"In-text #edb25e4e","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"74fd07c53dbd400a5a8feb2632053294d5b69c7bbf1cf71fe11525939c844be5","prominence":"central","quote":{"exact":"Kleene closure"},"quote_capped":false,"section":["Closure properties"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Kleene closure","segments":[{"text":"Kleene closure"}]},"unresolved":null},{"absence":null,"basis":"03c81913f7437b28531495d4eb0e028878821a7607c774f82bfc9de13a62287c","coverage":null,"id":"enwiki-653406-1366106761::In-text #9308e26c","item":"In-text #9308e26c","kind":"definition","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.mem_accepts","end_line":256,"library":"mathlib","line":255,"location_key":"7948e8dbc313cf39f22c04fb7643731aa623cb57a302d666cef1a49e0f76092d","module":"Mathlib.Computability.NFA","note":"Lean reads being in an accepting state at the end as the evaluated set of reachable states meeting the set of accepting states, and allows an arbitrary state type where the article keeps a finite one.","pair_key":"d208bf248be527ee4b502bc6de65740e9464a370bf165dfb45e583dff5fbfdf6","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.mem_accepts {α : Type u} {σ : Type v} {M : NFA α σ} {x : List α} : x ∈ M.accepts ↔ ∃ S ∈ M.accept, S ∈ M.evalFrom M.start x"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.accepts","end_line":253,"library":"mathlib","line":253,"location_key":"03c81913f7437b28531495d4eb0e028878821a7607c774f82bfc9de13a62287c","module":"Mathlib.Computability.NFA","note":"This is the defined object behind the acceptance rule, given for an arbitrary state type and so for more machines than the article's finite ones.","pair_key":"f6c57827791bf5e17d809cc06858a3571a52b0a1a11801611a349dcb286fbbee","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"2dbc726b9277cc9bbe5cf0a82655cae918b6e09e7f458e31eaf0328e96a431fe","prominence":"supporting","quote":{"exact":"If, when the automaton has finished reading, it is in an accepting"},"quote_capped":true,"section":["Properties"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.","segments":[{"text":"If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string."}]},"unresolved":null},{"absence":null,"basis":"c98804e6d3cc3a2515e8531e4abd98245f957708817c6bcda167681e398404ab","coverage":null,"id":"enwiki-653406-1366106761::In-text #848a61c6","item":"In-text #848a61c6","kind":"definition","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.accepts","end_line":253,"library":"mathlib","line":253,"location_key":"c98804e6d3cc3a2515e8531e4abd98245f957708817c6bcda167681e398404ab","module":"Mathlib.Computability.NFA","note":"Lean packages the collection as a language over the alphabet and allows any state type, which covers more machines than the article's finite ones.","pair_key":"a3e64e927a4f6bba07c741c00e56046d63a755966bddbe5be738d31f7aeb0a3d","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.accepts {α : Type u} {σ : Type v} : NFA α σ → Language α"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"f8ebfea17834cebf340706263d78aa83e49830a1d61ca9f305c55f324445daab","prominence":"supporting","quote":{"exact":"The set of all strings accepted by an NFA is the language"},"quote_capped":true,"section":["Properties"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"The set of all strings accepted by an NFA is the language the NFA accepts.","segments":[{"text":"The set of all strings accepted by an NFA is the language the NFA accepts."}]},"unresolved":null},{"absence":null,"basis":"4ed4627220bcbe6c52be61d83f8cb94844346f7eb6facf3dc2b2acceffdcf54d","coverage":null,"id":"enwiki-653406-1366106761::In-text #3105ee88","item":"In-text #3105ee88","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"medium","declaration":"NFA.toDFA_correct","end_line":315,"library":"mathlib","line":312,"location_key":"4ed4627220bcbe6c52be61d83f8cb94844346f7eb6facf3dc2b2acceffdcf54d","module":"Mathlib.Computability.NFA","note":"Mathlib states the subset construction for an arbitrary state type and leaves the step to the word regular to the definition of a regular language, which asks exactly for a deterministic machine with finitely many states.","pair_key":"dc9a765c7e94c44c95e45681f3b1b487020afe03b0c3ff073e797aa6b9c111e7","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"Language.isRegular_iff","end_line":374,"library":"mathlib","line":372,"location_key":"45040fa5dbb502fe829b414269fe188dfbccf540a511ac9299a9d28d9427fa94","module":"Mathlib.Computability.DFA","note":"It fixes what being regular means, a finite-stated deterministic machine accepting the language, but says nothing about machines that are nondeterministic.","pair_key":"22b4c55e7f51765537cb7428fb43436352368e3d8caba798295893eb0bc0f226","path":"Mathlib/Computability/DFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem Language.isRegular_iff {T : Type u} {L : Language T} : L.IsRegular ↔ ∃ σ x M, M.accepts = L"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"e922c610cf95df176788131e7ab8b60e0940bccaf0a89eb715ec796a17c6d803","prominence":"supporting","quote":{"exact":"This language is a regular language."},"quote_capped":false,"section":["Properties"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"This language is a regular language.","segments":[{"text":"This language is a regular language."}]},"unresolved":null},{"absence":null,"basis":"85b8db2656068b64258a9ab32aef59891ddc4e20677efadffd8376dbef781299","coverage":null,"id":"enwiki-653406-1366106761::In-text #6aa08ab3","item":"In-text #6aa08ab3","kind":"theorem","locations":[{"challenge":"survived","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA_correct","end_line":315,"library":"mathlib","line":312,"location_key":"85b8db2656068b64258a9ab32aef59891ddc4e20677efadffd8376dbef781299","module":"Mathlib.Computability.NFA","note":"Mathlib names the deterministic machine instead of merely asserting that one can be found, and states it for an arbitrary state type, so it covers more machines than the article's finite ones.","pair_key":"69df436e9f5397fc89efab1b689e2eb6e2bde7b1d9040216fec6b01ec933b2a4","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"broadMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts"},"statement":false},{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA","end_line":309,"library":"mathlib","line":306,"location_key":"a3ba7a2bab358af831e7b98630c5698f7fa0772d6f2e95a01331e5c8a9a5a946","module":"Mathlib.Computability.NFA","note":"It is the subset construction itself, data rather than a claim, and on its own says nothing about the language of the machine it builds.","pair_key":"611df3a336da4c135dc9ea599d306e36f1adfba5020f16f00bd51ec9dcdc6066","path":"Mathlib/Computability/NFA.lean","proof_status":"definition","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"def NFA.toDFA {α : Type u} {σ : Type v} : NFA α σ → DFA α (Set σ)"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"7eab5323a3b281c021eed506a6ffa4627b259d0bd52d2d98460807db775dacea","prominence":"supporting","quote":{"exact":"For every NFA a deterministic finite automaton (DFA) can be found that"},"quote_capped":true,"section":["Properties"],"status":"formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.","segments":[{"text":"For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":3,"queries":4,"sha256":"71f85982832df00e61e1617a5557658704c42161e4c223e6b18caddea0752c5e"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #59b1c947","item":"In-text #59b1c947","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"ca22f14035db9ef142e36a92af1a0812ac22ba632f58281fa7ab0e5a654726a3","prominence":"supporting","quote":{"exact":"Each step requires at most s2 computations, where s is the number"},"quote_capped":true,"section":["Implementation"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"Each step requires at most s2 computations, where s is the number of states of the NFA.","segments":[{"text":"Each step requires at most s2 computations, where s is the number of states of the NFA."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":4,"queries":4,"sha256":"0be8a2631afdcf90cc35a564f438bf7ca8b2f1d2ac76bccdb6eaad05346be3dc"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #0a0c162f","item":"In-text #0a0c162f","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"cb73b214cc679f79154b03e2c122d5f0a3cb7523e772f218b3f448a2628e88fe","prominence":"supporting","quote":{"exact":"A string of length n can be processed in time O(ns2),[15] and"},"quote_capped":true,"section":["Implementation"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"A string of length n can be processed in time O(ns2),[15] and space O(s).","segments":[{"text":"A string of length n can be processed in time O(ns2),"},{"ref":"[15]"},{"text":" and space O(s)."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"c538c3b2ac38e8ea2157c6ea7b797fc5d472b3cbdedb59db5d930db4b14f3782"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #f9a7462f","item":"In-text #f9a7462f","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"59f7529510b596128f00802b13a8f507a69c2c7ff913fe0c6df413b245863a16","prominence":"supporting","quote":{"exact":"(This, too, requires linear storage with respect to the number of NFA"},"quote_capped":true,"section":["Implementation"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"(This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)","segments":[{"text":"(This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)"}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"8725087e8ec87ac86f8b98b22ff2ab4a0bd820cdaef53b318d13d3b9c2957354"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #fdbb1154","item":"In-text #fdbb1154","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"34bb4e6004541c8def2e232df17b5b1bf1602982ec58420dd426b4fb541deeb4","prominence":"central","quote":{"exact":"One can solve in linear time the emptiness problem for NFA, i.e.,"},"quote_capped":true,"section":["Complexity"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"One can solve in linear time the emptiness problem for NFA, i.e., check whether the language of a given NFA is empty.","segments":[{"text":"One can solve in linear time the emptiness problem for NFA, i.e., check whether the language of a given NFA is empty."}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"00e356120198fd3ee0d16ef16afde0d91335cad4379f38746c9751a1b28f5850"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #32dd99bd","item":"In-text #32dd99bd","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"4f6492a6e5810272df7c272d03c814476b02ca84ed5b3ad247eceab84f9895ee","prominence":"central","quote":{"exact":"It is PSPACE-complete to test, given an NFA, whether it is universal,"},"quote_capped":true,"section":["Complexity"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"It is PSPACE-complete to test, given an NFA, whether it is universal, i.e., if there is a string that it does not accept.[17]","segments":[{"text":"It is PSPACE-complete to test, given an NFA, whether it is universal, i.e., if there is a string that it does not accept."},{"ref":"[17]"}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"cd052a28a68d85e2014382ad952947faa58425cdd38c648bf11d8e7937724e65"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #94177626","item":"In-text #94177626","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"31269f36537ce71dffcdfb447b549978485817ec45885c9244c3ac18010a4b9f","prominence":"supporting","quote":{"exact":"As a consequence, the same is true of the inclusion problem, i.e.,"},"quote_capped":true,"section":["Complexity"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"As a consequence, the same is true of the inclusion problem, i.e., given two NFAs, is the language of one a subset of the language of the other.","segments":[{"text":"As a consequence, the same is true of the inclusion problem, i.e., given two NFAs, is the language of one a subset of the language of the other."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"ac64e7dfe44bcba56d2326a676c382de4157c45dcf7fd56b7735dbc33991bd17"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #ff419391","item":"In-text #ff419391","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"5de38b8906da9796fb258188477d859ddf2e4dcf8cfe74f198360c9fec6e7dcb","prominence":"supporting","quote":{"exact":"Given as input an NFA A and an integer n, the counting"},"quote_capped":true,"section":["Complexity"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"after":{"layer":"; it is #P-hard.","segments":[{"text":"; it is #P-hard."}]},"layer":"Given as input an NFA A and an integer n, the counting problem of determining how many words of length n are accepted by A is intractable","segments":[{"text":"Given as input an NFA A and an integer n, the counting problem of determining how many words of length n are accepted by A is intractable"}]},"unresolved":null},{"absence":{"challenge":"survived","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"6e5742eb9cb6a0b36998d411490eaaf26fff5b6145c63ed98db937774f41e329"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #8eebf256","item":"In-text #8eebf256","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"e7167191db4397853b7918fe1cf930f20b5e71faa0d1cfced94dda5ca0bbd2cc","prominence":"supporting","quote":{"exact":"it is #P-hard."},"quote_capped":false,"section":["Complexity"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"before":{"layer":"Given as input an NFA A and an integer n, the counting problem of determining how many words of length n are accepted by A is intractable; ","segments":[{"text":"Given as input an NFA A and an integer n, the counting problem of determining how many words of length n are accepted by A is intractable; "}]},"layer":"it is #P-hard.","segments":[{"text":"it is #P-hard."}]},"unresolved":null},{"absence":{"challenge":"sampled_out","libraries":48,"receipt":{"candidates":2,"queries":3,"sha256":"3674e658f36257c2734c38b77dd91a1dfd05955133a727f12ad77eb44131d691"},"universe":"u1","universe_sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"basis":null,"coverage":null,"id":"enwiki-653406-1366106761::In-text #84a32fa1","item":"In-text #84a32fa1","kind":"theorem","locations":[],"outcome":"absent","passage_ends_in_suffix":false,"passage_key":"221a61a5eddc1a3a1a1cef19d23e9d0b39e8376e13bc630fa863afa484b02a66","prominence":"supporting","quote":{"exact":"In fact, this problem is complete (under parsimonious reductions) for the complexity"},"quote_capped":true,"section":["Complexity"],"status":"not_formalized","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"In fact, this problem is complete (under parsimonious reductions) for the complexity class SpanL.","segments":[{"text":"In fact, this problem is complete (under parsimonious reductions) for the complexity class SpanL."}]},"unresolved":null},{"absence":null,"basis":"6f4d2d18b3a5d5e146d0514dc984c2aa137e6054c4500b232c7894275302b334","coverage":null,"id":"enwiki-653406-1366106761::In-text #b7656351","item":"In-text #b7656351","kind":"theorem","locations":[{"challenge":"sampled_out","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"NFA.toDFA_correct","end_line":315,"library":"mathlib","line":312,"location_key":"6f4d2d18b3a5d5e146d0514dc984c2aa137e6054c4500b232c7894275302b334","module":"Mathlib.Computability.NFA","note":"This gives the direction from a nondeterministic machine to a deterministic one; the reverse direction of the stated equivalence is not asserted here.","pair_key":"d1cad8ed1028b9ce564024b9d8a0524d7430f7b9e680dc4b10d2ac165090c222","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":1,"relation":"hasPart","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem NFA.toDFA_correct {α : Type u} {σ : Type v} {M : NFA α σ} : M.toDFA.accepts = M.accepts"},"statement":false},{"challenge":"downgraded","commit":"3dfb8e22b67042b31fac228dee0e1169a1a7820f","confidence":"high","declaration":"DFA.toNFA_correct","end_line":354,"library":"mathlib","line":348,"location_key":"db2807c42f6532b941109e131e4ae159ebc437ca94d238c8396a51c30fad3312","module":"Mathlib.Computability.NFA","note":"This gives only the converse direction, from a deterministic machine to a nondeterministic one, and not the direction handled by the subset construction.","pair_key":"880804f9260c657aceaed6772a924a3d851cf6a9d6f70bfc21180cdceb69abfd","path":"Mathlib/Computability/NFA.lean","proof_status":"proved","rank":2,"relation":"relatedMatch","repo":"https://github.com/leanprover-community/mathlib4","signature":{"elided":false,"text":"theorem DFA.toNFA_correct {α : Type u} {σ : Type v} (M : DFA α σ) : M.toNFA.accepts = M.accepts"},"statement":false}],"outcome":"located","passage_ends_in_suffix":false,"passage_key":"5b744065b94affd23afe6330aeb3e0903e8cd342ac90621d20ef15995ffde5e5","prominence":"supporting","quote":{"exact":"NFAs and DFAs are equivalent in that if a language is recognized"},"quote_capped":true,"section":["Application of NFA"],"status":"partial","subject_uri":"https://en.wikipedia.org/w/index.php?curid=653406&oldid=1366106761","text":{"layer":"NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa.","segments":[{"text":"NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa."}]},"unresolved":null}],"provenance":{"challenge":{"harvested":"2026-11-01T14:25:17Z","mode":"locate-challenge","model":"claude-opus-5","model_name":"Claude Opus 5","operator":"jack","reviewer_model":"claude-opus-5","reviewer_model_name":"Claude Opus 5","run_id":"chal-tierA-b1","sampling":{"absence_sample_rate":0.25,"sample_rate":0.2,"seed":0,"strong_sample_rate":0.5},"skill_commit":"d85385aa4eb2818373e9b6b8b41b765ffaf53750","started":"2026-11-01T03:19:32Z"},"inventory":{"harvested":"2026-10-30T20:00:47Z","mode":"locate-inventory","model":"claude-opus-5","model_name":"Claude Opus 5","operator":"jack","reviewer_model":"claude-opus-5","reviewer_model_name":"Claude Opus 5","run_id":"inv-tierA-b1r","skill_commit":"d85385aa4eb2818373e9b6b8b41b765ffaf53750","started":"2026-10-30T07:23:03Z"},"locate":{"harvested":"2026-11-01T03:06:57Z","mode":"locate","model":"claude-opus-5","model_name":"Claude Opus 5","operator":"jack","reviewer_model":"claude-opus-5","reviewer_model_name":"Claude Opus 5","run_id":"loc-tierA-b1b","skill_commit":"d85385aa4eb2818373e9b6b8b41b765ffaf53750","started":"2026-10-31T04:59:09Z"}},"reader":{"bytes":264691,"images":[{"author":"Headbomb","file":"Lock-gray-alt-2.svg","licence":"CC0","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/deed.en","project":"commons"},{"author":"User:Trappist the monk","file":"Lock-green.svg","licence":"CC0","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/deed.en","project":"commons"},{"author":"VulpesVulpes42, Headbomb","file":"Lock-red-alt-2.svg","licence":"CC0","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/deed.en","project":"commons"},{"author":"Ashutosh y0078","file":"NFASimpleExample.svg","licence":"CC BY-SA 3.0","licence_url":"https://creativecommons.org/licenses/by-sa/3.0","project":"commons"},{"author":"Jochen Burghardt","file":"NFASimpleExample_Runs10.gif","licence":"CC BY-SA 4.0","licence_url":"https://creativecommons.org/licenses/by-sa/4.0","project":"commons"},{"author":"Jochen Burghardt","file":"NFASimpleExample_Runs1011.gif","licence":"CC BY-SA 4.0","licence_url":"https://creativecommons.org/licenses/by-sa/4.0","project":"commons"},{"author":"Interiot","file":"NFAexample.svg","licence":"Public domain","licence_url":null,"project":"commons"},{"author":"Niels Mündler","file":"Relatively_small_NFA.svg","licence":"CC0","licence_url":"https://creativecommons.org/publicdomain/zero/1.0/deed.en","project":"commons"},{"author":"Trapmoth","file":"Thompson-or.svg","licence":"CC BY-SA 3.0","licence_url":"https://creativecommons.org/licenses/by-sa/3.0","project":"commons"}],"marks":524,"passages":88,"sha256":"f818e8aa71e17fabb19be7d7e816be52225ba37d79a82d7da416dac1d72baf7d","unplaced":[]},"record_set":"23710337d053e8212378a9e580805628bcdfda61a6fc431e65f24a4a16c9e602","records_sha256":"97e4aa38e1bb9a0b49a6fe124e4570affcc6f264796f56028b2b368ecc346eeb","revision":1366106761,"schema":"wikilean.articles.article/1","seal":{"created":"2026-11-01T14:25:17Z","schema":"cf-locate-recordset/2","set_id":"tierA-b1b","skill_commit":"d85385aa4eb2818373e9b6b8b41b765ffaf53750","status_rule":3},"source":{"html_sha256":"2b68332db9f10f500f6c685a859824af38814ed0beee9ec0d7d9c6ea52068f1c","layer_sha256":"ee086a74baf50c5d9880bf03d62840db383450d8b6485fe229aaa4b0fa68b501","renderer":"web-html/3"},"source_id":"enwiki-653406-1366106761","summary":{"by_library":{"mathlib":{"complete":66,"incomplete":0,"locations":66,"passages":48,"related":40}},"by_prominence":{"central":{"by_status":{"formalized":15,"not_formalized":7,"partial":10,"statement_only":0,"unresolved":0},"passages":32},"subject":{"by_status":{"formalized":1,"not_formalized":0,"partial":0,"statement_only":0,"unresolved":0},"passages":1},"supporting":{"by_status":{"formalized":18,"not_formalized":33,"partial":4,"statement_only":0,"unresolved":0},"passages":55}},"by_proof_status":{"definition":37,"proved":69},"by_relation":{"broadMatch":46,"closeMatch":3,"exactMatch":1,"hasPart":11,"narrowMatch":5,"relatedMatch":40},"by_status":{"formalized":34,"not_formalized":40,"partial":14,"statement_only":0,"unresolved":0},"locations":66,"passages":88,"related":40},"supplements":{"audit_summary":{"schema":"wikilean.articles.audit-summary/1","sha256":"53b29c5773caa9a3a339ccb36db38548137820e05477c4eff49dfb63a91b74df"},"passage_text":{"schema":"wikilean.articles.passage-text/1","sha256":"c0c740562cd14bdcabe43ac1d7ba81039d8e41ef850fd199d7151de6bb774885"},"provenance":{"schema":"wikilean.articles.provenance/1","sha256":"ea245b590ba9078bc0b79003dc1e311dc1421475fe49483e3e3a905ed7c7ec4e"},"reader_html":{"schema":"wikilean.articles.reader-html/1","sha256":"738196c11695087fc8e74590f5ac362acd61af48a8950c0a049559dd3902d2df"},"signatures":{"corpus_built":"2026-10-18T06:14:30Z","corpus_sha256":"a364fd6aede529da1c9f2fa13fda6230a26381f27dafc8801c4205e2b5cf5221","schema":"wikilean.articles.signatures/1","sha256":"2ebb5eebf8b2ebd1f615518abce6169661140cc54d5fcad5f4443150cc62d874","universe":"u1"}},"title":"Nondeterministic finite automaton","universe":{"frozen":"2026-10-17","id":"u1","libraries":48,"sha256":"12e9eacf66816a249dcecba39f20dd7ca977c042af3e6acdb16ac7a45a4a9e76"},"wikidata":"Q617295"}
