Tuấn Sơn

[CODE]Câu 1: A). s1 -> as1 ->aas1 ->aaas1 ->aaaa L(G1) = {an/ n>=1} S2-> bs2cc/ ba S2 -> bs2cc ->bbs2cc ->bbbs2ccc ->bbbbaccc LG2 = {bmbacm/ m>=0} B). LG3 = { anbmbacm / n>=1, m>=0}. Câu 2: A. L= anbm ab (n>=0, m>=0) Xây dựng DFA thừa nhận L Khả năng xảy ta: 1. DFA đã đọc xâu ab, sau đó nó có thể thừ nhận xâu vào. 2. DFA chưa bao giờ đọc ký tự a, nhưng có đọc ít nhất 1 ký tự b, nó có thể đọc ký tự b cho đến khi gặp ký tự a đầu tiên, thì nó có thể đọc ngay sau đó ký tự b đi liền. 3. DFA chưa bao giờ đọc ký tự b, nhưng đã đọc ít nhất 1 ký tự a nó có thể đọc ký tự a cho đến khi gặp ký tự b thì kết thúc. Nhận xét: Trường hợp (1) ứng với trạng thái thừa nhận, ký hiệu q2, Trường hợp (2) ứng với trạng thái đầu q0. Trường hợp (3) ứng với trạng thái đầu q1. δ(q0,a)=q1 δ(q0,b)=q0 δ(q1,a)=q1 δ(q1,b)=q2 δ(q2,a)=q1 δ(q2,b)=q0  M = {q0, q1,q2}, (a,b),δ, q0, {q2} Δ(q0,abbab) = δ(q1,bbab) = δ(q2,bab) = δ(q0,ab) = δ(q1,b)=q2 q2 € F -> ω thuộc stomat vừa xây dựng.

B. δ a b ->q0 (q1,q2) q1 q1 q2 (q0q2) *q2 фs q2 δ(q0,a) = δ{q1,q2} δ(q0,b) = q1 δ({q1,q2},a)= δ(q1,a) ν δ(q2,a) = (q2, ф) δ({q1,q2},b)= δ(q1,b) ν δ(q2,b) = (q0,q1,q2) δ(q1,a) = q2 δ(q1,b) = (q0,q1) δ(q2,a) = ф δ(q2,b) = q2 δ({q0,q1},a)= δ(q0,a) ν δ(q1,a) = (q1,q2) δ({q0,q1},b)= δ(q0,b) ν δ(q1,b) = (q1,q0) δ({q0,q1,q2},a)= δ(q0,a) ν δ(q1,a) ν δ(q2,a) = {q1,q2} δ({q0,q1,q2},b)= δ(q0,b) ν δ(q1,b) ν δ(q2,b) = {q1,q2} δ’ a b ->q0 {q1,q2} Q1 q1q2 q2 {q0,q1,q2} q1 q2 {q0,q1} *q2 Ф q2 q0q1 q1q2 q0,q1 *q0q1q2 q1q2 q0,q1,q2

Đặt: q0 = p0 {q0,q1} = p3 q1 = p1 {q1,q2}= p4 q2 = p2 {q0,q1,q2}= p5 δ’ a b ->p0 P4 P1 P4 P2 P5 P1 P2 P3 *p2 Ф p2 P3 P4 P3 *p5 P4 P5

Văn phạm sinh bởi ngôn ngữ trên - chưa đọc ký tự b nào, đọc ít nhất 1 ký tự tiếp tục đọc ký tự a hoặc b  chuyển sang trang thái thừa nhận. - chưa đọc ký tự a nào, đọc ít nhất 1 ký tự b đọc ký tự a chuyển sang thừa nhận. - L(G) = XaBn (n>=1) (gồm các ký tự X có thể là a hoặc b bất kỳ).

Bài 3: Các luật sau trong G thỏa mãn dạng chuẩn chomsky được đưa vào G’: S -> a A ->B/SB A -> a B -> BA/b Luật chưa chuẩn: S->aB A -> bAb B->bBB Đặt: V1 =BB Va =a Vb=b  S ->VaB
A->VbAVb V1 -> BB B ->VbV1 Va -> a, Vb ->b Luật chuẩn: S ->VaB
V1 -> BB B ->VbV1 Va -> a, Vb ->b Luật chưa chuẩn: A->VbAVb Đặt V2=AVb => A->VbV2 V2->AVb Vậy chuyển về dạng Chomsky: S -> a A ->B/SB A -> a B -> BA/b S ->VaB
V1 -> BB B ->VbV1 Va -> a, Vb ->b [/CODE]