hoang_quan735
New Member
Chia sẻ miễn phí cho các bạn tài liệu: BÀI TẬP LỚN MÔN AUTOMAT: MINH HỌA HÀM DỊCH CHUYỂN MỞ RỘNG CỦA DFA
1.
Định nghĩa Hàm Dịch Chuyển Mở Rộng:
Hàm Dịch Chuyển Mở Rộng được định nghĩa đệ quy trên độ dài của xâu w
như sau: δ* (q, ε) = q, với mọi trạng thái q, nếu DFA không đọc kí hiệu vào nào thì sẽ
vẫn ở trạng thái cũ.
δ* (q, w) = δ* (δ* (q, x), a), với w=xa, x Є ∑* và a Є ∑.
Theo như định nghĩa ta có thể thực hiện cài đặt Hàm Dịch Chuyển Mở Rộng bằng
giải thuật đệ quy. Sau mỗi lần đọc 1 ký tự trong số chuỗi đưa vào, kích thước bài toán lại giảm đi.
Trường hợp suy biến là khi Hàm Dịch Chuyển đọc đến ký tự cuối cùng.
2. Mô tả bằng giả ngôn ngữ lập trình:
procedure read(String chuoiKiTu)
if (độ dài xâu kí tự vào = 1)begin
for (cặp p trong số các cặp <
begin
if (p có Trạng Thái == Trạng Thái Hiện Tại
&& Kí Tự == Kí Tự Được Đọc)
begin
Trạng Thái Hiện Tại = các cặp <,
Trạng Thái>.get(p);
if (Trạng Thái Hiện Tại là Trạng Thái Kết Thúc)begin
Automat đón nhận ngôn ngữ
endelsebegin
Automat không đón nhận ngôn ngữ
end
end
end
endelse
begin
for (cặp p trong số các cặp <
begin
if (p.Key là trạng thái hiện tại &&
p.Value là kí tự vào)
begin
trạng thái hiện tại = các cặp trạng thái[p];break;
Hàm Dịch Chuyển Mở Rộng được định nghĩa đệ quy trên độ dài của xâu w như sau:. • δ* (q, ε) = q, với mọi trạng thái q, nếu DFA không đọc kí hiệu vào nào thì sẽ v
Dành riêng cho anh em Ketnooi, bác nào cần download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
1.
Định nghĩa Hàm Dịch Chuyển Mở Rộng:
Hàm Dịch Chuyển Mở Rộng được định nghĩa đệ quy trên độ dài của xâu w
như sau: δ* (q, ε) = q, với mọi trạng thái q, nếu DFA không đọc kí hiệu vào nào thì sẽ
vẫn ở trạng thái cũ.
δ* (q, w) = δ* (δ* (q, x), a), với w=xa, x Є ∑* và a Є ∑.
Theo như định nghĩa ta có thể thực hiện cài đặt Hàm Dịch Chuyển Mở Rộng bằng
giải thuật đệ quy. Sau mỗi lần đọc 1 ký tự trong số chuỗi đưa vào, kích thước bài toán lại giảm đi.
Trường hợp suy biến là khi Hàm Dịch Chuyển đọc đến ký tự cuối cùng.
2. Mô tả bằng giả ngôn ngữ lập trình:
procedure read(String chuoiKiTu)
if (độ dài xâu kí tự vào = 1)begin
for (cặp
begin
if (p có Trạng Thái == Trạng Thái Hiện Tại
&& Kí Tự == Kí Tự Được Đọc)
begin
Trạng Thái Hiện Tại = các cặp <
Trạng Thái>.get(p);
if (Trạng Thái Hiện Tại là Trạng Thái Kết Thúc)begin
Automat đón nhận ngôn ngữ
endelsebegin
Automat không đón nhận ngôn ngữ
end
end
end
endelse
begin
for (cặp
begin
if (p.Key là trạng thái hiện tại &&
p.Value là kí tự vào)
begin
trạng thái hiện tại = các cặp trạng thái[p];break;
Hàm Dịch Chuyển Mở Rộng được định nghĩa đệ quy trên độ dài của xâu w như sau:. • δ* (q, ε) = q, với mọi trạng thái q, nếu DFA không đọc kí hiệu vào nào thì sẽ v
Dành riêng cho anh em Ketnooi, bác nào cần download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí