Chương 2 -Automat Hữu Hạn

Introductory ExampleChúng ta hãy tạo ra một ngôn ngữ nhỏ gấn như ngôn ngữ PascalTrong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệlà một tập tất cả các chuỗi được bắt đầu là một ký tự và theo saulà một số lượng tùy ý các ký tự hay ký số. , ||l a|b|… 0|1…, , , và là các biếna, b, …, 0, 1, … là những ký tự kết thúc
Nội dung trích xuất từ tài liệu:
Chương 2 -Automat Hữu Hạn Automat Hữu HạnFinite Automata Dr. Huỳnh Trung Hiếu Faculty of Information Technology HoChiMinh City University of IndustryIntroductoryExample Chúng ta hãy tạo ra một ngôn ngữ nhỏ gần như ngôn ngữ Pascal. Trong ngôn ngữ này, giả thiết rằng một định danh câu lệnh hợp lệ là một tập tất cả các chuỗi được bắt đầu là một ký tự và theo sau là một số lượng tùy ý các ký tự hay ký số. ,  ||λ  a|b|…  0|1…  , , , và là các biến a, b, …, 0, 1, … là những ký tự kết thúcIntroductoryExample Một dẫn xuất cho định danh x1 => => x => x => x1 => x1Biểu diễn Automat Dùng đồ thị: Các nút là các trạng thái nội.  Các cạnh là các chuyển dịch.  Nhãn của các cạnh cho biết điều gì xảy ra.  a 1 2IntroductoryExampleAnautomatonthatacceptsalllegalPascalidentifiers: Letter yes 1 2 Digit Letter or Digit no 3 Letter or Digit 5DeterministicFiniteAutomata(DFA) MộtaccepterhữuhạnđơnđịnhhaymộtDFAđược địnhnghĩabởibộnăm: M=(Q,∑,δ ,q0,F) Q:finitesetofinternalstates ∑:finitesetofsymbolsinputalphabet δ :Q× ∑→Q transitionfunction q0∈Q:initialstate F⊆ Q:setoffinalstates 6OperationalManner Tại thời điểm ban đầu, nó được giả định đang ở trong trạng thái Input file bắt đầu q0, với cơ chế nhập đang ở tại ký hiệu bên trái nhất của chuỗi nhập vào. Trong mỗi lần di chuyển của automat, đầu đọc tiến về phía Control unit phải một ký hiệu. q0 Khi gặp ký hiệu kết thúc chuỗi, chuỗi nhập được chấp nhận nếu như automat đang ở một trong yes/no những trạng thái kết thúc của nó. Ngược lại thì chuỗi bị từ chối. 7TransitionGraphs M=(Q,∑,δ ,q0,F) |Q|vertices(circles) Edge(qi,qj)labelledaforδ (qi,a)=qj Initialverticleq0 Finalvertices(doublecircles)inF 8Example1 M=({q0,q1,q2},{0,1},δ ,q0,{q1}) δ (q0,0)=q0 δ (q0,1)=q1 δ (q1,0)=q0 δ (q1,1)=q2 δ (q2,0)=q2 δ (q2,1)=q1 1 0 0 0 q0 q1 q2 1 1 Dfa này chấp nhận chuỗi 001, 011, 010???. 9ExtendedTransitionFunction δ *:Q× ∑*→Q extendedtransitionfunctionNếuδ (q0,a)=q1vàδ (q1,b)=q2thìδ *(q0,ab)=q2Mộtcáchhìnhthức,chúngtađịnhnghĩaδ *đệquynhưsau:δ *(q,λ )=q δ *(q,wa)=δ (δ *(q,w),a) 10LanguagesandDFAsNgôn ngữ được chấp nhận bởi một dfa M; 11Example1 M=({q0,q1,q2},{a,b},δ ,q0,{q1}) a a, b b a, b q0 q1 q2 L(M)=? 12Example1 M=({q0,q1,q2},{a,b},δ ,q0,{q1}) a a, b b a, b q0 q1 q2 trap state Không thoát được L(M)={a b|n≥ 0} n 13Theorem 14Example2 Tìm một acce ...