Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Công Nghệ Thông Tin
Kỹ thuật lập trình
Lecture Theory of automata - Lecture 40
Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Theory of automata - Lecture 40
Anh Thái
80
17
ppt
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
The following will be discussed: Recap of example of PDA corresponding to CFG, CFG corresponding to PDA. Theorem, HERE state, Definition of Conversion form, different situations of PDA to be converted into conversion form. | Recap lecture 39 PDA corresponding to CFG, Examples of PDA corresponding to CFG Example Consider the following CFG S XY X aX | bX |a Y Ya | Yb | a First of all, converting the CFG to be in CNF, introduce the nonterminals A and B as A a B b The following CFG is in CNF Example continued S XY X AX | BX |a Y YA | YB | a A a B b The PDA corresponding to the above CFG will be PH S AT ST RD1 a RD2 A PP ∆ Y ∆ RD3 RD5 PH Y PH X PH X PH B X a a PH X PH A S RD4 b B PH A PH Y PH B PH Y X X Y Y Theorem Given a PDA that accepts the language L, there exists a CFG that generates exactly L. Before the CFG corresponding to the given PDA is determined, the PDA is converted into the standard form which is called the conversion form. Before the PDA is converted into conversion form a new state HERE is defined which is placed in the middle of any edge. CFG corresponding to PDA continued Like READ and POP states, HERE states are also numbered e.g. becomes RD7 RD9 a RD7 HERE3 a RD9 b b Conversion form of PDA Definition: A PDA is in conversion form if it fulfills the following conditions: There is only one ACCEPT state. There are no REJECT states. 3. Every READ or HERE is followed immediately by a POP i.e. every edge leading out of any READ or HERE state goes directly into a POP state. CFG corresponding to PDA No two POPs exist in a row on the same path without a READ or HERE between them whether or not there are any intervening PUSH states (i.e. the POP states must be separated by READs or HEREs). All branching, deterministic or nondeterministic occurs at READ or HERE states, none at POP states and every edge has only one label. CFG corresponding to PDA Even before we get to START, a “bottom of STACK” symbol $ is placed on the STACK. If this symbol is ever popped in the processing it must be replaced immediately. The STACK is never popped beneath this symbol. Right before entering ACCEPT this symbol is popped out and left. CFG corresponding to PDA 7. The PDA must begin with the sequence The entire input string must be read before the machine can accept the word. Different situations of a PDA to be converted into conversion form are discussed as follows START PUSH $ HERE POP $ CFG corresponding to PDA contd. becomes RD7 POP a b PUSH b PUSH a PUSH $ RD7 a b $ b RD7 RD8 a b b To satisfy condition 3, CFG corresponding to PDA contd. becomes To satisfy condition 4, POP4 POP5 a b POP4 HERE a POP5 b CFG corresponding to PDA contd. RD1 POP1 a RD2 RD3 a b To satisfy condition 5 becomes as follows CFG corresponding to PDA contd. RD1 POP2 a RD2 b POP3 a RD3 a CFG corresponding to PDA contd. RD1 POP a PUSH a PUSH b RD2 a b RD1 POP1 PUSH a PUSH b RD2 a b POP2 a a To satisfy condition 5 becomes CFG corresponding to PDA contd. $ STACK To satisfy condition 6, it is supposed that the STACK is initially in the position shown below Summing Up Recap of example of PDA corresponding to CFG, CFG corresponding to PDA. Theorem, HERE state, Definition of Conversion form, different situations of PDA to be converted into conversion form
TÀI LIỆU LIÊN QUAN
Lecture Theory of automata - Lecture 33
Lecture Theory of automata - Lecture 34
Lecture Theory of automata - Lecture 35
Lecture Theory of automata - Lecture 36
Lecture Theory of automata - Lecture 37
Lecture Theory of automata - Lecture 38
Lecture Theory of automata - Lecture 39
Lecture Theory of automata - Lecture 40
Lecture Theory of automata - Lecture 41
Lecture Theory of automata - Lecture 42
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.