Thư viện tài liệu, ebook tổng hợp lớn nhất Việt Nam

Định lý 6.4: Nếu L được chấp nhận bởi một PDA chấp nhận chuỗi bởi Stack rỗng thì L là ngôn ngữ phi ngữ cảnh Cách xây dựng: Đặt G(V, T, P, S) là CFG, trong đó: • V là tập các đối tượng dạng [q, A, p] Đặt PDA M(Q, Σ, Γ, δ, q0, Z0, Ø) chấp nhận L với Stack rỗng • S là ký hiệu bắt đầu mới được thêm vào • P là tập các luật sinh dạng 1. S → [q0, ...

16 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1049 | Lượt tải: 0

Bổ đề bơm: cho L là một CFL bất kỳ, tồn tại một số n chỉ phụ thuộc vào L sao cho nếu z  L và |z| ≥ n thì ta có thể viết z=uvwxy sao cho: |vx| ≥ 1, |vwx| ≤ n và i ≥ 0 ta có uviwxiy  L Ví dụ: chứng minh L = {aibici | i ≥ 1} không là CFL • Giả sử L là CFL, khi đó tồn tại số n theo bổ đề bơm • Xét chuỗi z = anbncn, |z| ≥ n, ta có thể viết z=uvw...

27 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1253 | Lượt tải: 0

Một phép toán là đóng đối với tập chính quy khi áp dụng chúng vào tập hợp chính quy thì vẫn giữ được các tính chất của tập chính quy. Định lý 4.3: tập hợp chính quy đóng với các phép toán: hợp, nối kết và bao đóng Kleen. Định lý 4.4: tập hợp chính quy đóng với phép lấy phần bù. Định lý 4.5: tập hợp chính quy đóng với phép giao

9 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1129 | Lượt tải: 0

• Ta sẽ chứng minh (quy nạp theo k) bổ đề sau: với mọi Rkij đều tồn tại một biểu thức chính quy ký hiệu cho Rkij .  k = 0: R0 ij là tập hữu hạn các chuỗi 1 ký hiệu hoặc   Giả sử ta có bổ đề trên đúng với k-1, tức là tồn tại BTCQ rk-1lm sao cho L(rk-1lm) = Rk-1lm  Vậy đối với Rkij ta có thể chọn BTCQ rk ij = (rk-1ik)(rk-1kk)*(rk-1kj) + r...

34 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1038 | Lượt tải: 0

Automata đơn định (Deterministic Automata): • Mỗi bước di chuyển chỉ được xác định duy nhất bởi cấu hình hiện tại (hàm chuyển của automata là đơn trị) Automata không đơn định (Non-deterministic Automata): • Tại mỗi bước di chuyển, nó có vài khả năng để lựa chọn (hàm chuyển của automata là đa trị)

18 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1141 | Lượt tải: 0

Cây: là đồ thị có hướng • 1 nút gốc • Nút trung gian (nút trong) • Nút lá: không dẫn ra nút con • Thứ tự duyệt trên cây: trái  phải

20 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1060 | Lượt tải: 0

Bài tập 6.7. Một xí nghiệp sản xuất máy tính có xác suất làm ra phế phẩm là 0,02. Chọn ngẫu nhiên 50 máy để kiểm tra, tìm xác suất để: a. Có đúng 2 phế phẩm. b. Có không quá 2 phế phẩm. Bài tập 6.8. Xác suất để gặp một hạt thóc lép khi chọn giống là 0,004. Tìm xác suất để khi chọn ngẫu nhiên 1000 hạt trong vô số thóc ta gặp: a. 10 hạt lép. b...

61 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1899 | Lượt tải: 0

Tính chất 3.16. Hàm đặc trưng của biến ngẫu nhiên X xác định duy nhất hàm mật độ xác suất . Nói cách khác hai biến ngẫu nhiên có chung hàm đặc trưng thì chúng sẽ có chung hàm mật độ. Tính chất 3.17. Nếu hàm đặc trưng ϕ(t) của biến ngẫu nhiên liên tục X là giới hạn của dãy hàm ϕn(t) của biến ngẫu nhiên Xn thì hàm phân phối xác suất F(x) của X l...

56 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1228 | Lượt tải: 0

Phương sai là kuf vopngj của bình phưng các sai lệch giữa X và E, nói cách khác phương sai là trung bình phương sai lệch, nó phản ánh mức độ phân tán các giá trị của biến ngẫu nhiên xung quanh giá trị trung bình Trong công nghiệp phương sai biểu thị độ chính xác trong san xuất

29 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1026 | Lượt tải: 0

BTVT” với hàm mục tiêu cực đại Có mô hình giống BTVT, nhưng hàm mục tiêu cực đại. • Dấu hiệu tối ưu: ∆ ≥ ∀ ij 0, ( , ) i j • Chọn ô • Nếu có ô cấm , thay , với là số dương rất lớn. • Chọn ô có lớn nhất phân phối trước. ( , ) i j * * ∆ = ∆ ∆ < i j * * min{ : 0} ij ij ( , ) i j c M ij = − M cij

30 trang | Chia sẻ: nguyenlam99 | Ngày: 15/01/2019 | Lượt xem: 1386 | Lượt tải: 0