定義1.1：有窮自動機是乙個 5 元組 ( q, , , q0, f )，其中(1) q 是乙個有窮集合，稱為狀態集。
(2) 是乙個有窮集合，稱為字母表。(3) : qq是轉移函式。
(4) q0q 是起始狀態。(5) fq 是接受狀態集。
定義1.7：如果乙個語言被一台有窮自動機識別，則稱它是正則語言。
dfa和nfa的區別：1、dfa每個狀態對於字母表中的每個符號總是恰好有乙個轉移箭頭射出。nfa乙個狀態對於字母表中的每乙個符號可能有0個1個或多個射出的箭頭；2、在dfa中，轉移箭頭上的標號是取自字母表的符號。
而nfa的箭頭可以標記字母表中的符號或。
定義1.17：非確定型有窮自動機 (nfa) 是乙個 5 元組 ( q, , , q0, f )，其中(1) q 是有窮的狀態集。
(2) 是有窮的字母表。(3) : qεp(q)是轉移函式。
(4) q0q 是起始狀態。(5) fq 是接受狀態集。
正規表示式的形式化定義：稱 r 是乙個正規表示式，如果 r 是(1) a，這裡 a 是字母表中的乙個元素；(2) ；(3)
(4) r1∪r2，這裡 r1 和 r2 是正規表示式；(5) r1r2 ，這裡 r1 和 r2 是正規表示式；(6) r1* ，這裡 r1 是正規表示式；
定義1.33：gnfa m = (q, , , qstart, qaccept)（1）q 是有窮的狀態集。
(2) 是輸入字母表。(3) :(q-)(q-) r 是轉移函式。
(4) qstart 是起始狀態。(5) qaccept 是接受狀態。其中 r 是正規表示式。
定理1.37（幫浦引理）：若 a 是乙個正則語言，則存在乙個數 p (幫浦長度) 使得，如果 s 是 a 中任一長度不小於 p 的字串，那麼 s 可以被分成 3 段，s = xyz，滿足下述條件：
(1) 對於每乙個 i 0, xyiz∈a ；(2) | y | 0；(3) | xy | ≤ p
上下文無關文法：(1) 寫下起始變元——第一條規則左邊的變元。(2) 取乙個已寫下的變元，並找到以該變元開始的規則，把這個變元替換成規則右邊的字串。
(3) 重複步驟2，直到寫下的字串沒有變元。
定義2.1：上下文無關文法是乙個 4 元組 ( v, , r, s )，且(1) v 是乙個有窮集合，稱為變元集；(2) 是乙個與 v 不相交的有窮集合，稱為終結符集；(3) r 是乙個有窮規則集，每條規則由乙個變元和乙個由變元及終結符組成的字串構成；(4) sv 是起始變元。
如果 u = v ，或者存在 u1, u2, …, uk, k 0 使得u u1 u2… uk v，則稱 u 派生 v，記作 u * v。
最左派生：對於文法 g 中的乙個字串 w 的派生，如果在每一步都是替換左邊剩下的變元，則稱這個派生是最左派生。
定義2.4：如果字串 w 在上下文無關文法 g 中有兩個或兩個以上不同的最左派生，則稱 g 歧義地(ambiguously) 產生字串 w，如果文法 g 歧義地產生某個字串，則稱 g 是歧義的。
某些上下文無關語言只能用歧義文法產生，這樣的語言是固有二義的。
定義2.5：稱乙個上下文無關文法是為喬姆斯基正規化(chomsky normal form)，如果它的每乙個規則具有如下形式：
a bc a a其中 a 是任意的終結符，a、b 和 c 是任意的變元，且 b 和 c 不能同時是起始變元。此外，允許規則s ，其中 s 是起始變元。
定理2.6：任一上下文無關語言都可以用乙個喬姆斯基正規化的上下文無關文法產生。
定義2.8：pda是乙個6元組m=(q,σ,γ,δ, q0, f)，其中(1)q——狀態的有限集合。
(2)σ——輸入字母表。(3)γ——棧字母表。(4)δ：
狀態轉移函式，q×σε ×γε p（ q×γε ） 。(5)q0——q0∈q，開始狀態。 (6)f——fq，終止狀態集合。
定理2.12：乙個語言是上下文無關的，當且僅當存在一台下推自動機識別它。
引理2.13：如果乙個語言是上下文無關的，則存在一台下推自動機識別它。
引理2.15：如果乙個語言被一台下推自動機識別，則它是上下文無關的。
斷言2.16：如果apq產生x，則x能夠把p從p和空棧一塊帶到q和空棧。
斷言2.17：如果x能夠把p從p和空棧帶到q和空棧，則apq產生x。
定理2.19：如果a是上下文無關語言，則存在數p（幫浦長度），使得a中任何乙個長度不小於p的字串s都能被劃分為5段s = uvxyz且滿足下述條件：
1. 對於每乙個i 0, uvixyiz ∈a；2. |vy| 0；3.
|vxy| p。
定義3.1：tm是乙個7元組(q, , , , q0, qacc, qrej) ，其中：
（1）q ： 狀態集（2） ： 輸入字母表, 不包括空白字元（3） ：
帶字母表, and （4） ： 轉移函式 : q x q x x , （5）q0：
開始狀態（6）qacc： 接受狀態,（7） qrej：拒絕狀態。
格局：當前狀態q q 當前帶內容 * 讀寫頭位置
定義3.2：如果乙個語言能被某一圖靈機識別，則稱該語言是圖靈可識別的。
定義3.3：如果乙個語言能被某一圖靈機判定，則稱它是圖靈可判定的。
定理3.8：每個多帶圖靈機等價於某乙個單帶圖靈機
推論3.9：乙個語言是圖靈可識別的，當且僅當存在多帶圖靈機識別它。
定理3.10：每個非確定型圖靈機等價於某乙個確定圖靈機
推論3.11：乙個語言是圖靈可識別的，當且僅當存在非確定性圖靈機識別它。
推論3.12：乙個語言是可判定的，當且僅當存在非確定性圖靈機判定它。
定理3.13：乙個語言是圖靈可識別的，當且僅當有列舉器列舉
圖靈機描述：形式化描述：詳盡地寫出圖靈機的狀態、轉移函式等，屬於最低層次、最詳細程度的描述；實現描述：
使用日常語言描述圖靈機動作，如怎麼移動讀寫頭、怎麼在帶上儲存資料等，這種程度的描述沒有給出狀態和轉移函式的細節；高水平描述：也使用日常語言來描述演算法，但忽略了實現的模型，不需要提及機器怎樣管理它的帶子或讀寫頭。
定理4.1：adfa是乙個可判定語言。
定理4.2：anfa是乙個可判定語言。
定理4.3：arex 是乙個可判定語言。
定理4.4：edfa 是乙個可判定語言。
定理4.5：eqdfa是乙個可判定語言。
定理4.6：acfg是乙個可判定語言。
定理4.7：ecfg是乙個可判定語言。
定理4.8：每個上下文無關語言都是可判定的。
定理4.9：atm 是不可判定的。
定義4.10：設 a 和 b 是兩個集合，f 是從 a 到 b 的函式。
如果 f從不將兩個不同元素對映到同乙個物件，即：只要a ≠b 就有 f (a)≠f (b)，則稱 f 是一對一對映的。如果 f 能擊中 b 的每個元素，即：
對 b 的每個元素b，都存在 a a，使得 f (a) =b，則稱 f 是滿對映。如果存在函式 f：a b，f 是一對一對映又是滿對映，則稱集合 a 和 b 有相同規模。
而既是一對一對映又是滿對映的函式稱為對應。在對應中，a 的每個元素對映到 b 的唯一乙個元素，且 b 的每個元素都有a的唯一乙個元素對映到它。對應就是將 a 的元素與 b 的元素進行配對的方法。
定義4.12：如果乙個集合 a 是有限的或者與 n 有相同的規模，則 a 是可數的。
推論4.15：存在不能被任何圖靈可識別的語言。
定理4.16：乙個語言是可判定的，當且僅當它既是圖靈可識別的，也是補圖靈可識別的。
可以證明：如果乙個語言和它的補都是圖靈可識別的，則此語言也是可判定的。
這樣，對任何不可判定語言，它或它的補至少有乙個不是圖靈可識別的。
乙個語言的補是由不在此語言中的所有串構成的語言。
如果乙個語言是乙個圖靈可識別語言的補集，則稱它是補圖靈可識別的。
推論4.17： tm 不是圖靈可識別的。
定理5.1：halttm是不可判定的。
定理5.2：etm 是不可判定的。
定理5.3：regulartm是不可判定的。
定理5.4：eqtm是不可判定的。
定義5.5：設m是乙個圖靈機，w是乙個串。
m在w上的乙個接受計算歷史是乙個格局序列c1，c2，．．．,cl，其中c1是m在w上的起始格局，cl是m的乙個接受格局，且每個ci都是ci-1的合法結果，即符合m的規則。m在w上的一拒絕計算歷史可類似定義，只是cl應是乙個拒絕格局。
定義5.6：線性界限自動機是一種受到限制的圖靈機，它不允許其讀寫頭離開包含輸入的帶區域。
如果此機器試圖將它的讀寫頭移出輸入的兩個端點，則讀寫頭就保持在原地不動。這與普通圖靈機的讀寫頭不會離開帶子的左端點的方式一樣。
引理5.7：設m是有q個狀態和g個帶符號的lba。對於長度為 n的帶子，m恰有qngn個不同的格局。
定理5.8：alba是可判定的。
定理5.9：elba是不可判定的
定理5.10：allcfg是不可判定的。
定義5.12：函式f： * * 是乙個可計算函式，如果有圖靈機m，使得在每個輸入w上停機，且此時只有f(w)出現在帶上。
定義5.15：語言a是對映可歸約到語言b的，如果存在可計算函式 f： **使得對每個w，w∈a等價於f(w) ∈b記作a≤mb。稱函式f為a到b的歸約。
定理5.16：如果a≤mb且b是可判定的，則a也是可判定的。
推論5.17：如果a≤mb且a是不可判定的，則b也是不可判定的。
定理5.22：如果a≤mb，且b是可圖靈可識別的，則a也是圖靈可識別的。
推論5.23：如果a≤mb，且a不是圖靈可識別的，則b也不是圖靈可識別的。
定理5.24：eqtm既不是圖靈可識別的，也不是補圖靈可識別的。
引理6.1：存在可計算函式 q: * * ，對任意串w, q(w)是圖靈機pw的描述，pw列印出w，然後停機。
self的構造：（1）a部分首先執行，再根據完成情況將控制傳給b。a的任務是列印出b的描述。
b的任務是列印出a的描述。（2）先構造a部分（3）使用機器p來定義a，其中p用函式q在處的值q()描述，這樣，a部分是乙個列印出的圖靈機。a的描述依賴於是否已經有了b的描述，所以在構造出b之前，無法完成a的描述。
（4）對於b部分：從a產生的輸出來計算a（5）如果b能夠得到，就能應用q來得到。但b如何得到？
當a結束時，它被留在帶上。所以b只要看著帶子就能得到。計算q()=之後，b將之加到帶的前面。
然後將a和b組合成乙個機器並在帶上寫下它的描述=。
矩陣論定義定理總結
1.1定義 由個數組成的乙個n階行列式為 即所有取自不同行不同列的n個元素的乘積的代數和，其中每一項的符合由排列的奇偶性決定。n階行列式的展開原理 定義1.1.2在n階行列式d中，任選k行和 k列 將其交叉點上的個元素按原來位置排成乙個k階行列式m，稱為d的乙個k階子式。在d中劃去m所在之k行k列後...
小學生數學公式定理定義
乙個數除以分數等於這個數乘以分數的倒數。甲數除以乙數 0除外 等於甲數乘以乙數的倒數。分數的加 減法則 同分母的分數相加減，只把分子相加減，分母不變。異分母的分數相加減，先通分，然後再加減。分數的乘法則 用分子的積做分子，用分母的積做分母。什麼叫比 兩個數相除就叫做兩個數的比。如 2 5或3 6或1...
中考物理常用定理定律總結
22.電流越大,線圈匝數越多電磁鐵的磁性越強 有鐵心比無鐵心磁性要強的多 23.電磁繼電器的特點 通電時有磁性,斷電時無磁性 自動控制 24.發電機是根據電磁感應現象製成的,機械能轉化為電能 法拉第 25.電動機是根據通電導體在磁場中要受到力的作用這一現象製成的,電能轉化為機械能。26.產生感應電流...