Bài tập tìm bao đóng bắc cầu có lời giải

Full PDF PackageDownload Full PDF Package

This Paper

A short summary of this paper

37 Full PDFs related to this paper

Download

PDF Pack

Các hệ thống rời rạcPhạm Thị Thanh Loan14/24/2016Bộ môn TĐh - ĐH Mỏ Địa chấtBài tập chương 11.Hãy cho biết các thứ tự cho phép liệt kê các phần tử của cácngôn ngữ sau:{a, b}*{a}* {b}* {c}*{w| w{a,b}* và trong w số các a bằng số các b}Giải:4/24/2016{a, b}* = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb…. }{a}*{b}*{c}* = {ε, a, aa ….}{ε, b, bb…}{ε, c, cc…}= {ε, a, aa, b, bb, ab, abb, aab, aabb…} {ε, c, cc…}= {ε, a, aa, b, bb,c, cc, ac, acc, aac, aacc, bc, bcc, bbc,bbcc, abc, abcc, abbc, abbcc, aabc, aabcc, aabbc, aabbcc…}{w| w{a,b}* và trong w số các a bằng số các b}= {ε, ab, ba, aabb, bbaa…}Bộ môn TĐh - ĐH Mỏ Địa chất2Bài tập chương 12. Cho A = {0, 1, 2} và R = {[0,1],[1,2]}. Tìm R* và R+.Giải:R+ = {[0,1],[1,2], [0,2]}.R* = R0  R+.aR0b khi và chỉ khi a = bR* = {[0,1],[1,2], [0,2], [0,0], [1,1], [2,2]}.3. Tìm bao đóng truyền ứng, bao đóng phản xạ và truyền ứng, và baođóng đối xứng của quan hệ {[1,2],[2,3],[3,4],[5,4]}Giải:Bao đóng truyền ứng [] bắc cầu: R+ : {[1,2],[2,3],[3,4],[5,4], [1,3],[2,4], [1,4],}Bao đóng phản xạ và bắc cầu: R* :{[1,2],[2,3],[3,4],[5,4], [1,3],[2,4], [1,4], [1,1], [2,2], [3,3], [4,4], [5,5]}Bao đóng đối xứng: {[1,2],[2,3],[3,4],[5,4], [2,1], [3,2], [4,3],[4,5]}4/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất3Bài tập chương 21. Hãy mô tả bằng tiếng Việt các tập hợp chỉ định bởi các BTCQsau:[11+0]*[00+1]*[1+01+001]*[ε + 0+00]*Giải:[11+0]*[00+1]* chỉ định tập mọi xâu chứa số 1 và 0 trong đó 1 và 0không viết xen kẽ.[1+01+001]*[ε + 0+00]* chỉ định mọi xâu 0 và 1 không chứa 3 số 0liên tiếp ở đầu.Xây dựng BTCQ cho tập chuỗi chứa các số 0 và 1 xennhau [01]*4/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất4Bài tập chương 22. Cho M = [{0,1}, {q1, q2, q3}, , q1, {q3}] là NFA, trong đó  được cho bởi[q1, 0] = {q2, q3}, [q1, 1] = {q1}q2, 0] = {q1, q2}, [q2, 1] = [q3, 0] = {q2}, [q3, 1] = {q1, q2}Tìm DFA [M’] tương đương với MGiải:M’ = [S, Q’, ’, q1, F’] trong đó:Q’ = 2Q = {[, [q1], [q2], [q3], [q1,q2], [q1,q3], [q2,q3], [q1,q2,q3]}F’ = tập mọi trạng thái trong Q’ có chứa một trạng thái cuối nào đó của M= {{q3}, {q1,q3}, {q2,q3}, {q1,q2,q3}} kHàm chuyển ’: ’[[q1, q2,…qk]] =  [ qi , a ]i 1 ’[[q1], 0] = [q2, q3]; ’[[q1], 1 ] = [q1]; ’[[q2], 0] = [q1, q2]; ’[[q2], 1] =  ; ’[[q3], 0] = [q2]; ’[[q3], 1] = [q1, q2]; ’[[q1, q2], 0] = [q1, q2, q3]; ’[[q1, q2], 1] = [q1]; ’[[q1, q3], 0] = [q2, q3]; ’[[q1, q3], 1] = [q1, q2]; ’[[q2, q3], 0] = [q1, q2]; ’[[q2, q3], 1] = [q1, q2]; ’[[q1, q2, q3], 0] = [q1, q2, q3]; ’[[q1, q2, q3], 1] = [q1, q2];4/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất5Bài tập chương 2Hai biểu đồ chuyển của M và M’:11q100q204/24/201600,1q101001q310q3q2q1,q2,q30q1,q21Bộ môn TĐh - ĐH Mỏ Địa chất1 q1,q3 0q2,q30,16Bài tập chương 23. Tìm các FA đoán nhận các ngôn ngữ sau:Tập các xâu trên {0, 1} có chứa một số chẵn cácsố 0 và một số lẻ các số 1.Tập các xâu trong S* có độ dài chia đúng cho 3.Tập các xâu trên {0, 1} không chứa xâu con nàolà 10 cả4/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất7Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn }4/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất8Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn }S  {0,1}q04/24/2016q1Bộ môn TĐh - ĐH Mỏ Địa chất9Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1};q04/24/2016q1Bộ môn TĐh - ĐH Mỏ Địa chất10Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}q04/24/2016q1Bộ môn TĐh - ĐH Mỏ Địa chất11Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}0q04/24/2016q1Bộ môn TĐh - ĐH Mỏ Địa chất12Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}0q04/24/2016q1Bộ môn TĐh - ĐH Mỏ Địa chất13Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}1q04/24/20160q1Bộ môn TĐh - ĐH Mỏ Địa chất14Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}1q04/24/20160q1Bộ môn TĐh - ĐH Mỏ Địa chất15Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}1q04/24/201601q1Bộ môn TĐh - ĐH Mỏ Địa chất16Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}1q04/24/201601q1Bộ môn TĐh - ĐH Mỏ Địa chất17Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}11q10q004/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất18Bài tập chương 23.Giải:a. M1 = { x ∈{0,1}* | |0| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}1[q0,0] = q1 ; 1[q0,1] = q01[q1,0] = q0 ; 1[q1,1] = q111q10q004/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất19Bài tập chương 23.Giải:M2 = { x ∈{0,1}* | |1| lẻ} trong đó: S  {0,1}; Q2 = {a; b}; F2 = {a}2[a,0] = a ; 2[a,1] = b2[b,0] = b ; 2[b,1] = a0a01b14/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất20Bài tập chương 23.Giải:M2 = { x ∈{0,1}* | |1| lẻ} trong đó: S  {0,1}; Q2 = {a; b}; F2 = {a}2[a,0] = a ; 2[a,1] = b2[b,0] = b ; 2[b,1] = a0a01b14/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất21Bài tập chương 23.Giải:M = M1  M2 = [S, Q, , q0, F] trong đó:Q = Q1 x Q2 ; F = F1 x F2 ;1 x 2 ; q0 = [q0, a] Q = Q1 x Q2 = {[q0,a]; [q1,a]; [q0,b]; [q1,b]}; F = F1 x F2 = {[q0,b]}; q,j]  1q1,j], 2q2,j]]q0,a],0] = 1q0,0], 2a,0]][q1,a]; q0,a],1] = [q0,b]q0,b],0] = [q1,b]; q0,b],1] = [q0,a];q1,a],0] = [q0,a]; q1,a],1] = [q1,b];q1,b],0] = [q0,b]; q1,b],1] = [q1,a];11q0,a0q1,aq0,b0010q1,b14/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất22Bài tập chương 2b. M = { x ∈ S * | x chia hết cho 3}M = [S, Q, , q0, F] trong đó:Q = {q0; q1; q2;q3};F = {q3}; a = [1,4,7]; b = [2,5,8]; c = [0,3,6,9][q0,a] = q1; [q0,b] = q2 ; [q0,c] = q3[q1,a] = q2; [q1,b] = q3 ; [q1,c] = q1[q2,a] = q3; [q2,b] = q1 ; [q2,c] = q2[q3,a] = q1; [q3,b] = q2 ; [q3,c] = q3q0cbacq3ccaq1aq2bbab4/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất23Bài tập chương 2c. M = { x ∈{0,1}* | |x| chẵn hoặc tận cùng bằng 11}M1 = { x ∈{0,1}* | |x| chẵn } trong đó:S  {0,1}; Q1 = {q0; q1}; F1 = {q0}1[q0,0] = q1 ; 1[q0,1] = q01[q1,0] = q1 ; 1[q1,1] = q00,1q0q10,1M2 = { x ∈{0,1}* | |x| tận cùng là 11} trong đó:S  {0,1}; Q2 = {a; b;c}; F2 = {c}2[a,0] = a ; 2[a,1] = b2[b,0] = a ; 2[b,1] = c2[c,0] = a ; 2[c,1] = c10a1b01c0M = M1  M2 = [S, Q, , q0, F] trong đó: Q = Q1 x Q2 ; F = Q2 x F1 +Q1 x F2 ;  1 x 2 ; q0 = [q01, q02]4/24/2016Bộ môn TĐh - ĐH Mỏ Địa chất24Bài tập chương 2q0,a],0] = 1q0,0], 2a,0]][q1,a]; q0,a],1] = [q1,b]q0,b],0] = [q1,a]; q0,b],1] = [q1,c];q0,c],0] = [q1,a]; q0,c],1] = [q1,c];q1,a],0] = [q0,a]; q1,a],1] = [q0,b];q1,b],0] = [q0,a]; q1,b],1] = [q0,c];q1,c],0] = [q0,a]; q1,c],1] = [q0,c];q0,aq0,b0 104/24/20161q1,a0q0,c10 1q1,b0101q1,cBộ môn TĐh - ĐH Mỏ Địa chất25