Các cấu trúc đại số trong lý thuyết ôtômat

BỘ GIÁO DỤC VÀ ĐÀO TẠO

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN THỊ HỒNG NHUNG

CÁC CẤU TRÚC ĐẠI SỐ

TRONG LÝ THUYẾT ÔTÔMAT

Chuyên ngành: Phương pháp toán sơ cấp

Mã số: 60. 46. 40

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC

Đà Nẵng, Năm 2013

Công trình được hoàn thành tại

ĐẠI HỌC ĐÀ NẴNG

Người hướng dẫn khoa học: PGS.TS. Nguyễn Gia Định

Phản biện 1: Lê Hải Trung

Phản biện 2: Huỳnh Thế Phùng

Luận văn được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ khoa học họp tại Đại học Đà Nẵng vào ngày 25 tháng 5

năm 2013

Có thể tìm hiểu luận văn tại:

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Thư viện trường Đại học Sư Phạm, Đại học Đà Nẵng

1

MỞ ĐẦU

1. Lý do chọn đề tài

Đề tài này dành cho việc nghiên cứu các cấu trúc đại số liên

quan đến khái niệm Ôtômat. Tầm quan trọng được thực hiện trên

khung đại số của Ôtômat và cơ sở dữ liệu thực. Vì vậy, các khái niệm

này xuất hiện dưới dạng các cấu trúc đại số nhiều loại, cho phép lý

thuyết đại số được phát triển. Vì việc xử lý về mặt cấu trúc đại số mở

đường cho cấu trúc và dáng điệu của Ôtômat và cơ sở dữ liệu thực,

chúng ta hy vọng rằng lý thuyết được xây dựng sẽ tìm thấy các ứng

dụng của nó. Mặt khác, chúng ta theo đuổi khá nhiều mục đích đại số

hầu tìm kiếm các phương cách làm phong phú cho chính đại số.

Xuất phát từ nhu cầu phát triển của lý thuyết Ôtômat cùng

những ứng dụng của nó, chúng tôi quyết định chọn đề tài với chủ đề:

Các cấu trúc đại số trong lý thuyết Ôtômat để tiến hành nghiên cứu.

Chúng tôi hy vọng tạo được một tài liệu tham khảo tốt cho những

người bắt đầu tìm hiểu về Lý thuyết Ôtômat và các ứng dụng của nó

và luận văn đã chỉ ra được một số ví dụ minh hoạ đặc sắc nhằm góp

phần làm phong phú thêm các kết quả trong lĩnh vực này.

2. Mục đích nghiên cứu của đề tài

Mục tiêu của đề tài nhằm nghiên cứu lý thuyết Ôtômat qua các

cấu trúc đại số trên một số Ôtômat cụ thể.

3. Nhiệm vụ nghiên cứu

- Nghiên cứu về Ôtômat thuần tuý.

- Nghiên cứu về xây dựng và phân rã Ôtômat.

- Nghiên cứu về Ôtômat tuyến tính.

4. Đối tượng và phạm vi nghiên cứu

Đối tượng nghiên cứu của đề tài là các cấu trúc đại số trên một

số Ôtômat cụ thể. Phạm vi nghiên cứu của đề tài là lý thuyết Ôtômat.

2

5. Phương pháp nghiên cứu

- Thu thập các bài báo khoa học và tài liệu của các tác giả nghiên

cứu liên quan đến các cấu trúc đại số trong lý thuyết Ôtômat, cụ thể

là Ôtômat thuần túy, Ôtômat phổ dụng, Ôtômat Moore, Ôtômat thuần

túy tự do, Ôtômat tuyến tính, song Ôtômat.

- Tham gia các buổi seminar của thầy hướng dẫn để trao đổi các

kết quả đang nghiên cứu. Trao đổi qua email, blog, forum với các

chuyên gia về lý thuyết Ôtômat.

6. Ý nghĩa khoa học và thực tiễn của đề tài

- Tổng quan các kết quả của các tác giả đã nghiên cứu liên quan

đến lý thuyết Ôtômat và các cấu trúc đại số trên một số Ôtômat cụ thể

nhằm xây dựng một tài liệu tham khảo cho những ai muốn nghiên cứu

các cấu trúc đại số trong lý thuyết Ôtômat.

- Chứng minh chi tiết và làm rõ một số mệnh đề, cũng như đưa

ra một số ví dụ minh hoạ đặc sắc nhằm làm cho người đọc dễ dàng

tiếp cận vấn đề được đề cập.

7. Cấu trúc của luận văn

Ngoài các phần danh mục hình vẽ, lời cam đoan, mục lục, luận

văn chia thành 3 chương:

- Trong Chương 1, chúng tôi sẽ trình bày cấu trúc đại số của

Ôtômat thuần túy, Ôtômat phổ dụng, Ôtômat Moore, Ôtômat thuần

túy tự do.

- Trong Chương 2, chúng tôi sẽ trình bày việc xây dựng và phân

rã Ôtômat qua các Ôtômat thuần túy và thuần túy hữu hạn.

- Ôtômat tuyến tính dự kiến trình bày trong Chương 3. Cụ thể

là Ôtômat tuyến tính, song Ôtômat, xây dựng và phân rã Ôtômat tuyến

tính và tự đẳng cấu của Ôtômat tuyến tính và song Ôtômat.

3

CHƯƠNG 1

ÔTÔMAT THUẦN TUÝ

1.1. CÁC KHÁI NIỆM CƠ BẢN

1.1.1. Định nghĩa

Một ôtômat ��=(A, X, B) gồm ba tập A, X, B lần lượt được gọi

là tập các trạng thái, tập các tín hiệu vào, tập các tín hiệu ra và hai phép

toán hai ngôi:



: A x X→A, ∗ : A x X→B

Một ôtômat �� = (A, Γ, B) được gọi là ôtômat nửa nhóm nếu tập

các tín hiệu vào là một nửa nhóm, và thoả mãn:

a

 γ1γ2 = (a

 γ1)



γ2 (1.1)

a ∗ γ1γ2 = (a

 γ1) ∗ γ2,

1.1.2. Biểu diễn ôtômat của một tập và nửa nhóm

Cho ôtômat ��=(A, X, B) và nửa nhóm S(A, B). Phần tử xX

hoạt động, theo một cách như là phép biến đổi của tập hợp A, nghĩa là

phần tử của SA, và theo một cách khác như là phần tử của Fun(A, B).

Do đó ta định nghĩa hai ánh xạ:

α: X→SA, β: X→Fun(A, B). Với mỗi xX ta định nghĩa chuyển

đổi x

α

của SA và ánh xạ x

β

của Fun(A, B) theo cách sau:

ax

α = a



x, ax

β = a∗x.

Định nghĩa biểu diễn f: X→S(A, B), bằng cách đặt xf = (x

α

x

β

).

Biễu diễn này là liên kết với ôtômat ��. Nếu X=Γ là một nửa nhóm,

dễ dàng thấy rằng f: X→S(A, B) là đồng cấu từ nửa nhóm Γ vào S(A,

B).

Mặt khác, ta xét ánh xạ f: X→S(A, B) và phần tử x

f =

(φ, ψ)S(A,B)= SA x Fun(A, B) là ảnh của phần tử x. Ôtômat ��=(A,

4

X, B,

 , ∗) với a



x=x

φ, a∗x=a

ψ tương ứng với ánh xạ này. Nếu X=Γ

là một nửa nhóm, đồng cấu f: Γ→S(A, B) xác định ôtômat nửa nhóm

(A, Γ, B). Thật vậy, định nghĩa ôtômat ��= (A, X, B) tương đương với

việc xác định biểu diễn f: X→S(A, B) trong việc xác định ôtômat nửa

nhóm (A, Γ, B) là tương đương với đồng cấu f: X→S(A, B).

1.1.3. Đồng cấu ôtômat

Bộ ba ánh xạ μ=(μ1

,μ2

,μ3

), với μ1

:A→A

'

, μ2

:X→X

'

, μ3

:B→B'

được gọi là đồng cấu μ: ��→��’ từ ôtômat ��= (A, X, B) đến ôtômat

��’ = (A’, X’, B’), nếu điều kiện sau được thoả mãn:

(a



x)

μ1 = a

μ1 

x

μ2

(a ∗ x)

μ3 = a

μ1 ∗ x

μ2, aA, xX. (1.2)

Để định nghĩa đồng cấu của ôtômat nửa nhóm

μ: (A, Γ, B)→ (A′, Γ′, B′) và có thêm điều kiện sau:

μ2

là đồng cấu của nửa nhóm Γ đến Γ′. (1.3)

Mệnh đề 1.1. Bất kỳ đồng cấu ôtômat μ=(μ1

,μ2

,μ3

) nào đều có

thể được biểu diễn như tích μ = μ̃

3

μ̃

1

μ̃

2

của đồng cấu theo tín hiệu

ra μ̃

3

, theo trạng thái μ̃

1

và theo tín hiệu vào μ̃

2

.

Mệnh đề 1.2. Cho φ là đồng cấu từ ôtômat �� vào ôtômat �� và

ρ là đồng cấu tự nhiên �� lên ��/Kerφ. Khi đó ôtômat là �� đẳng cấu

với ôtômat �� /Kerφ, và tồn tại duy nhất đẳng cấu ψ sao cho ρψ = φ.

1.1.3. Ôtômat tuần hoàn

Mệnh đề 1.4. Nếu ôtômat con A’ = (A’, Γ’, B’) của (A, Γ, B)

sinh bởi hệ sinh (Z, X, Y) thì Γ’ là nửa nhóm con của Γ sinh bởi tập

X; tập A’ là hợp của tập Z với Z



Γ gồm a



γ, a ∈A', γ ∈ Γ'. Tập B’

là hợp của tập Y với tập tất cả các phần tử a * γ, với a ∈ A

'

, γ ∈ Γ'.

Chứng minh là hiển nhiên.

Mệnh đề 1.5. Mỗi ôtômat tuần hoàn với nửa nhóm Γ là đẳng

cấu với ôtômat thương nào đó của ôtômat Atm(Γ).

5

Mệnh đề 1.6. Mỗi ôtômat tuần hoàn rút gọn ��=(A, Γ, B) là

đẳng cấu với ôtômat Atm ̅̅̅̅̅̅(ψ: Γ → B) nào đó.

1.2. ÔTÔMAT PHỔ DỤNG

1.2.1. Định nghĩa các tính chất của ôtômat phổ dụng

Mệnh đề 2.1. Với bất kỳ ôtômat nửa nhóm �� = (A, Γ, B) tồn

tại duy nhất đồng cấu theo tín hiệu vào μ: ��→Atm1

(A, B).

Mệnh đề 2.2. Với bất kỳ ôtômat �� = (A, Γ, B), tồn tại duy nhất

một đồng cấu theo trạng thái μ: ��→Atm2

(Γ, B).

Mệnh đề 2.3. Với ôtômat bất kỳ ��= (A, Γ, B), tồn tại duy nhất

một đồng cấu theo tín hiệu ra từ Atm3

(A, Γ) vào �� (nghĩa là Atm3

(A,

Γ) là một vật đầu trong phạm trù các ôtômat với biểu diễn (A, Γ) cố

định ).

1.2.2. Tính khớp của ôtômat phổ dụng và rút gọn trái, phải

Mệnh đề 2.4.

a) Ôtômat Atm3

(A, Γ) là khớp nếu và chỉ nếu với (A, Γ) đã cho

tồn tại ít nhất một ôtômat khớp (A, Γ, B).

b) Ôtômat Atm3

(A, Γ) là rút gọn trái nếu và chỉ nếu với (A, Γ)

được cho tồn tại ít nhất một ôtômat (A, Γ, B) rút gọn trái.

Mệnh đề 2.5. Ôtômat Atm3

(A, S(A, B) là đẳng cấu với ôtômat

(A, S(A,B), AxB).

1.3. ÔTÔMAT MOORE

1.3.1. Định nghĩa và vài thuộc tính

Một ôtômat được gọi là Ôtômat Moore nếu tồn tại một ánh xạ

ψ: A → B sao cho: a*x = (a ๐ x)ψ. Ánh xạ ψ là ánh xạ xác định của

Ôtômat Moore. Điều kiện a*x = (a ๐ x)ψ có nghĩa là trong ôtômat

Moore toán tử ∗ mô phỏng bởi phép toán ◦ và ánh xạ ψ. Do đó ôtômat

Moore là dễ kiểm tra.

6

Mệnh đề 3.1. Ôtômat �� = (A, X, B) là ôtômat Moore nếu và

chỉ nếu công thức a1 ◦ x1= a2 ◦ x2 kéo theo a1 ∗ x1= a2 ∗ x2.

1.3.2. Ôtômat Moore và ôtômat phổ dụng

Mệnh đề 3.3. Nếu tập B không chỉ một phần tử thì với bất kì

A, ôtômat Atm1

(A, B) không phải là ôtômat Moore.

Bổ đề 3.4. Cho tập hợp Z và nửa nhóm Γ. Cho H=ZxΓ1

. Định

nghĩa biểu diễn (H, Γ): nếu h = (z, σ)H, zZ, σΓ

1 và σΓ, thì h∘γ

= (z, σγ). Khi đó:

a) Biểu diễn (H, Γ) là sinh tự do bởi tập Z, nghĩa là với bất kỳ

(A, Γ) ánh xạ υ: H→A có một mở rộng duy nhất đến ánh xạ υ: H→A

mà giao hoán với tác động của Γ trong H và A;

b) Nếu biểu diễn (H, Γ) được mở rộng đến ôtômat (H, Γ, B),

thì ôtômat này là Moore.

1.3.3. Đồng cấu của ôtômat Moore

Mệnh đề 3.5. Mỗi ôtômat là ảnh đồng cấu (theo trạng thái) của

ôtômat Moore.

Mệnh đề 3.6. Cho �� là ôtômat với ánh xạ xác định ψ và ρ = (ρ1,

ρ2, ρ3) là đồng dư của ��, thỏa mãn ρ1



kerψ khi đó ôtômat thương số

��/ρ cũng là một ôtômat Moore.

Mệnh đề 3.7. Nếu ρ là đồng dư Moore của ôtômat Moore �� thì ��/ρ

cũng là ôtômat Moore.

Mệnh đề 3.8. Đồng cấu µ của ôtômat Moore �� = (A, Γ, B) với

ánh xạ xác đinh ψ trên ôtômat ��’ = (A’, Γ’, B’) là một đồng cấu

Moore, nếu và chỉ nếu tồn tại ánh xạ ψ̃: A’→B’ với sơ đồ giao hoán.

1.4. ÔTÔMAT THUẦN TUÝ TỰ DO

1.4.1. Định nghĩa, sự thực thi

Xét phạm trù các

 - ôtômat thuần túy, mà vật là ôtômat thuần

túy với nửa nhóm cố định các tín hiệu tập vào  và cấu xạ là đồng

7

cấu có dạng (μ1, ��Γ, μ3), ở đây εΓ

là một ánh xạ đồng nhất của nửa

nhóm



. Một ôtômat (A,

 , B) được gọi là

 - ôtômat tự do với hệ

sinh tự do sinh (Z, Y), Z



A,Y



B, nếu cho bất kì

 - ôtômat ��’ =

(A’,



’, B’) và với mọi ánh xạ μ1

: Z



A’, μ3: Y



B’ tồn tại duy

nhất sự mở rộng của ánh xạ này đến đồng cấu μ=(μ1, ��Γ, μ3): ��



��’. Từ sự duy nhất của mở rộng kéo theo tính duy nhất (sai khác đẳng

cấu) của

 - ôtômat tự do �� với hệ sinh tự do (Z,Y).

1.4.2. Tiêu chuẩn tự do

Xét ôtômat �� = (A, Γ, B). Phần tử a



A được gọi là ước của

phần tử b



A nếu tồn tại phần tử γ



Γ, sao cho b = a ๐ γ.

Định lý 4.1. Ôtômat �� = (A, Γ, B) là tự do, đó là �� = Atm(Z,

X, Y), nếu và chỉ nếu điều kiện sau được thỏa mãn:

1) Với bất kì γΓ và aA phần tử a๐γ không phải là ước của a;

2) Với a, bA, γ1, γ2,γΓ, đẳng thức a๐γ=b๐γ kéo theo a=b và

đẳng thức a๐γ1= a ๐ γ2 kéo theo γ1=γ2;

3) Từ đẳng thức a ๐ γ1= b ๐ γ2 kéo theo hoặc a = b hoặc a là một

ước của b, hoặc b là một ước của a;

4) Mỗi phần tử aA chỉ có thể có một số hữu hạn các ước;

5) Đẳng thức a*γ1= b*γ2 kéo theo a ๐ γ1= b ๐ γ2.

1.3.4. Một vài tính chất

Mệnh đề 4.2. Cho τ là hạt nhân của ôtômat rút gọn AtmГ(Z,

Y)=(H, Г, Φ) và h1 = (z1,γ1) là phần tử của H. Khi đó h1τh2 nếu và chỉ

nếu z1 = z2 và γ1ργ2.

Mệnh đề 4.3. Nếu ôtômat (H,X,Φ) là tự do trong lớp của ôtômat

với tập hợp bất kỳ của tín hiệu vào, thì mỗi ôtômat con trong (H,X,Φ)

cũng là tự do.

8

1.5. TỔNG QUÁT HOÁ

1.5.1. Ôtômat với đa tạp tùy ý

Cho θ là một đa tạp của Ω đại số. Một bộ ba (A, X, B) với phép

toán ๐:AxX→A, *: AxX→B được gọi là ôtômat trong đa tạp θ, nếu A,

B là đại số của θ và với mỗi xX ánh xạ a→a๐x và a→a∗x, aA là

đồng cấu đại số của θ.

Ôtômat nửa nhóm trong đa tạp θ là có được theo cách tương tự.

Nếu μ=(μ1,μ2,μ3) là đồng cấu ôtômat trong đa tạp θ, thì μ1,μ3 được giả

sử là đồng cấu của ôtômat của đại số tương ứng của θ. Như trong mục

1, ta có thể giới thiệu các kiểu đặc biệt của ôtômat (theo tín hiệu vào,

theo tín hiệu ra, theo trạng thái), thiết lập một phân rã chính tắc và xây

dựng ôtômat phổ dụng tương ứng với cặp A, B của đại số tương ứng

ôtômat Atm1

(A,B)=(A, End(A, B), B) mà khác với ôtômat thuần túy

tương tự bằng End(A, B) = EndAxHom(A, B), ở đây EndA là tập hợp

tất cả các tự đồng cấu của đại số A và Hom(A,B) là tập hợp tất cả đồng

cấu từ A vào B. Tích trong End(A, B) là được xác định như trong S(A,

B) (xem 1.1.2). Phép toán ° và * được xác định như ôtômat Atm1

(A,B)

cho trường hợp thuần túy. Cho mỗi ôtômat �� = (A, Γ, B) trong đa tạp

θ chỉ có một đồng cấu trong tập vào �� →Atm1

(A, B), đó là Atm1

(A,

B) là vật cuối trong phạm trù của ôtômat trong θ với A và B đã cho và

với đồng cấu trên tập vào như là đẳng cấu.

1.5.2. Ôtômat tuyến tính

Chúng ta đã giới thiệu ôtômat trên θ bất kỳ. Lấy đa tạp của

không gian tuyến tính trên trường K hoặc đa tạp của moduls trên vành

giao hoán như θ, chúng ta có ôtômat tuyến tính. Theo cách khác, một

ôtômat (A, X, B) là một tuyến tính nếu A và B là không gian tuyến

tính của trường K (hoặc modul trên vành) và ánh xạ A vào A, và A

9

vào B được định nghĩa theo phép toán ° và * là ánh xạ tuyến tính. Theo

nguyên tắc, chúng ta sẽ xét ôtômat trên lớp của không gian tuyến tính.

1.5.3. Ôtômat Affine

Cho A là vector không gian, a



A, ánh xạ â: A→A được định

nghĩa theo nguyên tắc: Nếu x



A thì xâ = x + a được gọi là chuyển

đổi am của không gian A tương ứng phần tử a. Quan hệ â1â2= a1+a2 là

hiển nhiên, do đó, chuyển đổi thành lập một nhóm đẳng cấu đối với

nhóm phụ của không gian A. Kí hiệu nhóm này là Â. Rõ ràng để nhận

thấy rằng chuyển đổi là không phải chuyển đổi tuyến tính.

Xét không gian vector A và B, ánh xạ của dạng σ����, ở đây σ là

ánh xạ tuyến tính xét từ A vào B và bm là chuyển đổi của không gian

B tương ứng phần tử b



B được gọi là ánh xạ affine từ A vào B. Tập

hợp của tất cả ánh xạ affine từ A vào B là kí hiệu bởi Aff(A, B). Phần

tử của Aff(A, A) được gọi là chuyển đổi affine của không gian A. Nếu

σbm là ánh xạ affine từ A vào B và φ��̂từ B vào C thì tích của chúng

cũng là một ánh xạ affine từ A vào C, và có:

(σ��̂)(φ��̂)= σφ( bφ + c)m (5.1)

Tích này thỏa mãn tính chất kết hợp.

Không gian tuyến tính với ánh xạ affine như đẳng cấu dạng lớp.

Ôtômat trong phạm trù này được gọi là ôtômat affine. Nói cách khác,

một ôtômat affine là hệ thống (A, X, B, f), ở đây A, B là không gian

vector, X là một tập hợp, f là biểu diễn: X→Aff(A, A) x Aff(A, B)

định nghĩa của f là tương đương với hai biểu diễn α: X→Aff(A,A) và

β: A →Aff(A,B). Biểu diễn này tương ứng toán tử ° và *. Từ đây ta bỏ

qua ký hiệu f trên khái niệm ôtômat. Ôtômat nửa nhóm Affine �� =

(A, Γ, B) cũng được định nghĩa tương tự như vậy, nhưng biểu diễn α:

Γ→aff(A, A) và β: Γ→Aff(A,B) thõa mãn điều kiện sau:

1. α là đồng cấu nửa nhóm;