不確定的有限自動機（non-deterministic finite automaton）是2018年公布的計算機科學技術名詞。
基本介紹
- 中文名：不確定的有限自動機
- 外文名：non-deterministic finite automaton
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
有限自動機的一種類型。其中狀態轉換函式是一個多值函式，即在當前狀態下讀到一個輸入字元時，自動機的下一狀態可以是多個狀態中的某一個。
出處
《計算機科學技術名詞 》第三版。
不確定的有限自動機
相關詞條
- 不確定的有限自動機
不確定的有限自動機（non-deterministic finite automaton）是2018年公布的計算機科學技術名詞。定義有限自動機的一種類型。其中狀態轉換函式是一個多值函式，即在當前狀態下讀到一個輸入字元時，...
- 有限自動機
不確定的有限自動機NFA 若有限自動機根據當前所處的狀態和所面臨的輸入符號，能夠確定的後繼狀態不是唯一的，就稱這樣的有限自動機為不確定的有限自動機。如圖1所示是NFA，在這個NFA中，狀態0在輸入符號a時有兩個可能的轉移狀態0，1。我們一定已經注意到前述的DFA只是NFA的一種特殊情況，對於給定的輸入字元串w和...
- 不確定型有窮自動機
有窮自動機是一種有窮級數模型。它由一個讀頭和一條有窮長的紙帶所組成，紙帶被分割成有限個同樣大小的單元，每個單元中可以是空的，或寫有取自有窮字母表 上的一個字母，讀頭在每一時刻都對準一個單元，並具有一個確定的內部狀態，這些內部狀態構成一個有窮集 。其中指定一個（比如 q₁）為初始狀態，...
- 自動機
非確定有限自動機(NFA)自動機的狀態對字母表中的每個符號可以有也可以沒有轉移，對一個符號甚至可以有多個轉移。自動機接受一個字，如果存在至少一個從 q0 到 F 中標記(label)著這個輸入字的一個狀態的路徑。如果一個轉移是「未定義」的，自動機因此不知道如何繼續讀取輸入，則拒絕這個字。有ε轉移的非確定有限...
- 編譯原理與技術(第2版)(2014年北京郵電大學出版社有限公司出版的...
2.4.2不確定的有限自動機NFA 2.4.3從NFA到DFA的等價變換 2.4.4 DFA的小化 2.4.5從正規式到有限自動機 2.4.6有限自動機在計算機中的表示 2.5詞法分析的自動生成器Lex 2.5.1 Lex概述 2.5.2 Lex的語言與實現 練習2 第3章 程式語言的語法描述 3.1文法和語言 3.1.1文法的形式定義 3.1...
- 有限自動機理論
《有限自動機理論》是2007年電子科技出版社出版的圖書，作者是陳文宇。內容提要 《有限自動機理論》簡述了形式語言的基本內容，包括文法的分類和語言間運算的封閉性，有限自動機（包括有限狀態自動機、下推自動機和圖靈機）的基礎理論，從構造文法產生語言的角度和構造自動機識別語言的角度對語言進行討論，並介紹文法與...
- 形式語言,自動機理論與計算導論
3.1 確定有限狀態自動機(DFSA)45 3.2 不確定有限狀態自動機(NFSA)47 3.3 正則表達式51 問題與解答56 習題61 第4章 有限自動機:特徵、性質和可判定性65 4.1 有限自動機和正則文法65 4.2 正則集的泵浦引理66 4.3 封閉性68 4.4 可判定性定理70 問題和解答71 習題71 第5章 帶輸出的有限狀態自動機...
- 不確定時變非線性動態系統的分析與控制
研究如何提取時變非線性系統除無源度外的其他性能特徵。利用有限自動機對不確定時變非線性系統進行性能良好的控制。在無源性分析框架內研究時變非線性系統的H無窮控制。研究具有約束盚無窮控制應滿足的條件。給出一類時變非線性系統的H無窮控制設計方法。 [1]...
- 基於量子邏輯的不確定性計算模型及其套用研究
《基於量子邏輯的不確定性計算模型及其套用研究》是依託陝西師範大學，由韓召偉擔任項目負責人的青年科學基金項目。項目摘要 量子計算是計算機科學領域重要的研究方向，其中量子計算模型是其關鍵的科學問題之一。本項目擬採用語義分析方法，完善基於量子邏輯的計算理論：建立量子邏輯框架下的上下文無關文法、有限樹自動機、ω...
- 確定的有限自動機
確定的有限自動機 確定的有限自動機是2018年公布的計算機科學技術名詞 。 定義 有限自動機中的一種。這種有限自動機的狀態轉移函式是單值函式，即在一個狀態下掃描到一個輸入字元時轉移到狀態是唯一的。 出處 《計算機科學技術名詞 》。
- 編譯原理基礎
2.3.1 不確定的有限自動機（NondeterministicFiniteAutomata，NFA）2.3.2 確定的有限自動機（DeterministicFiniteAutomata，DFA）2.3.3 有限自動機的等價 2.4 從正規式到詞法分析器 2.4.1 從正規式到NFA 2.4.2 從NFA到DFA 2.4.3 最小化DFA 2.4.4 DFA的“短路”計算 2.4.5 由DFA構造詞法分析器 2...
- dfa
確定的有限自動機與有限機一樣，有一個有限狀態集合和一些從一個狀態通向另一個狀態的邊，每條邊上標記有一個符號，其中一個狀態是初態，某些狀態是終態。但不同於不確定的有限自動機，DFA中不會有從同一狀態出發的兩條邊標誌有相同的符號。DFA以如下方式接受或拒絕一個字元串：從初始狀態出發，對於輸入字元串...
- 編譯原理基礎與套用
3.4 有限狀態自動機 52 3.4.1 確定的有限狀態自動機 52 3.4.2 不確定的有限狀態自動機 56 3.4.3 NFA與DFA的轉化 57 3.4.4 正規表達式與有限狀態自動機的等價性 59 3.4.5 確定的有限狀態自動機的化簡 61 3.5 詞法分析程式的設計與實現 63 3.5.1 詞法分析程式的手工編寫 63 3.5.2 詞法分析...
- 離散數學(第七版)
12.3 語言和文法 12.4 不確定有限狀態自動機 12.5 語言和自動機之間的關係 注釋 本章複習 本章自測題 上機練習 第13章 計算幾何 13.1 最小距點對問題 13.2 計算凸包的一種算法 注釋 本章複習 本章自測題 上機練習 附錄a 矩陣 附錄b 代數學複習 附錄c 偽代碼 部分習題答案 參考文獻 符號表 ...
- 達納·斯科特
達納·斯科特與合作者麥可·拉賓（Michael Rabin）共同發表了論文《有限自動機和他們的決策問題》（Finite Automata and their Decision Problem），介紹了不確定性機器的概念，與標準圖靈機不同，不確定性機器可以在程式的每一步執行幾個不同的可能的“指令”，提出的不確定性機器的概念在研究領域被證明是有效的。他...
- 編譯原理簡明教程(第2版)
3.1.5 不確定有限自動機(NFA)3.1.6 由NFA 到DFA 的等價轉換 3.2 確定有限自動機DFA 的化簡 3.2.1 等價狀態和無關狀態 3.2.2 自動機的化簡 3.3 正則表達式形式定義 3.4 下推自動機PDA 3.4.1 下推自動機的機器模型 3.4.2 PDA 的形式定義 習題3 第4 章詞法分析 4.1 詞法分析概述 4.1.1...
- DNA計算及其在醫學領域中的套用
5．5．1 基因表達的不確定有限狀態自動機模型 5．5．2 不確定DNA有限狀態自動機的實現 6 容錯DNA計算及自修復機理 6．1 引言 6．2 DNA計算的自複製性 6．2．1 DNA片段自組裝 6．2．2 二維DNA分子元胞自動機 6．3 DNA計算的可逆性 6．3．1 基於DNA計算的布爾電路 6．3．2 可逆容錯門電路 6．3．...
- 計算機科學的數學基礎
第一部分 形式語言與自動機理論 第一章 語言與正規語言 1.1 符號、符號串及其運算 1.2 文法與語言的形式定義 1.3 正規表達式 1.4 正規文法與正規式 第二章 有限自動機 2.1 有限自動機的定義與構造 2.2 確定的有限自動機（DFA）2.3 不確定的有限自動機（NFA）2.4 NFA的確定化 2.5 DFA的最小化 2...
- 離散數學(第2版)(2011年清華大學出版社出版的圖書)
《離散數學（第2版）》是由賁可榮、袁景凌、高志華編著，2011年清華大學出版社出版的高等學校計算機教育規劃教材。該教材適合作為計算機和相關專業本科生“離散數學”的教學用書，亦可作為對離散數學感興趣的人員的參考書。全書共10章，主要包含數理邏輯、集合與關係、函式、組合計數、圖和樹、代數系統、自動機和初等數論...
- deterministic
adj. 確定性的；命運注定論的 短語搭配 deterministic model 確定性模型 deterministic chaos [數]決定性混沌；命定混沌（等於chaos）deterministic algorithm 確定性算法 ; 決定型演算法 ; 決定型算法 ; 演算法確定性 Deterministic Finite Automaton 確定有限狀態自動機 ; 確定性有限自動機 ; 自動機 ; 確定的有窮...
- 離散數學(第3版)(2021年清華大學出版社出版書籍)
《離散數學（第3版）》是清華大學出版社於2021年出版的書籍。內容簡介 離散數學是計算機科學與技術專業的一門重要基礎課。全書共10章，主要包含數理邏輯、集合與關係、函式、組合計數、圖和樹、代數系統、自動機和初等數論等內容。新增套用案例，闡明相應章節的知識可以解決什麼樣的典型套用問題。本書“歷史註記”可以...
- 布爾代數及其泛化結構
第16章 自動裝置的邏輯設計實例 16.1 典型實例解析 16.2 實例七則 第17章 布爾方程與布爾差分的套用 17.1 布爾方程的套用 17.2 布爾差分在自動診斷技術中的套用 第18章 布爾代數在事故樹分析中的套用 18.1 事故樹簡介 18.2 用於事故樹分析的布爾代數 第19章 有限自動機概述 19.1 有限自動機的基本概念 ...
