Ktl-icon-tai-lieu

Lý thuyết thông tin phần 2

Được đăng lên bởi Duy Khanh
Số trang: 5 trang   |   Lượt xem: 186 lần   |   Lượt tải: 0 lần
là số các ký hiệu tạo thành chuỗi
•

abca = 4
ký hiệu , là chuỗi không có ký hiệu nào

• Khái niệm ngôn ngữ

• |ε| = 0

• Cách biểu diễn ngôn ngữ

chuỗi v là chuỗi con của w nếu v ñược tạo
bởi các ký hiệu liền kề nhau trong chuỗi w.

• Văn phạm

• Chuỗi 10 là chuỗi con của chuỗi 0

• Sự phân lớp văn phạm

001

là chuỗi con bất kỳ nằm ở ñầu chuỗi
là chuỗi con bất kỳ nằm ở cuối chuỗi
• Chuỗi abc có các tiền tố a, ab, abc
1

là một thực thể trừu tượng mà ta
không ñịnh nghĩa ñược một cách hình thức

• Chuỗi 0246 có các hậu tố 6, 46, 246, 0246

3

là chuỗi ñược tạo thành bằng
cách viết chuỗi thứ nhất, sau ñó viết chuỗi thứ hai, ...

• Các chữ cái a, b, c … hoặc các số 1, 2, 3 …

•Nối ghép của chuỗi Long và Int là LongInt
•Nối kết của chuỗi rỗng: εw = wε = w (với mọi w)

• Là một tập (không rỗng) các ký hiệu nào ñó

→ ε là ñơn vị của phép nối kết

• Bộ chữ cái Latin {A, B, C, …, a, b, c, …, z}

của chuỗi w, ký hiệu wR, là chuỗi
w ñược viết theo thứ tự ngược lại.

một chuỗi (hay một từ - word) trên bộ
chữ cái Σ

•w = abcd → wR = dcba

εR = ε

• Là một dãy hữu hạn các ký hiệu của Σ
• Một ký hiệu có thể xuất hiện nhiều lần
Printed with FinePrint - purchase at 

2

4

L = Σ* - L

• Ngôn ngữ tự nhiên: tiếng Việt, tiếng Anh, …
• Ngôn ngữ lập trình: Pascal, C/C++, …

L1L2 = {w1w2 | w1 ∈ L1 và w2 ∈ L2} trên bộ chữ cái Σ1 ∪ Σ2

• Biểu thị các ý nghĩ, các sự kiện hay các khái niệm

• LLL…LL = L (kết nối i lần trên cùng ngôn ngữ L)

• Bao gồm một tập các ký hiệu và các quy tắc ñể
vận dụng chúng

• L = {ε}
0

i

• Là tập hợp các câu theo cấu trúc quy ñịnh nào ñó

5

∞

Bao ñóng Kleene: L* = ∪ L
=

L = L*L = LL*

●

Σ+ = Σ* - {ε}

Σ = {0,1} thì Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, …} và
6
Σ+ = {0, 1, 00, 01, 10, 11, 000, …}

Printed with FinePrint - purchase at 

L* = L ∪ {ε}

cho L = {a, ba}
• L = {aa, aba, baa, baba}
• L = {aaa, aaba, abaa, ababa, baaa,baaba, babaa, bababa}
• L* = {ε, a, ba, aa, aba, baa, baba, aaa, aaba, …} 8
3

Σ* = Σ+ + {ε}

1

Σ+ : tập hợp tất cả các chuỗi con, ngoại trừ chuỗi
rỗng ε, sinh ra từ bộ chữ cái Σ.

i

●

i

=

Σ* : tập hợp tất cả các chuỗi con, kể cả chuỗi rỗng
ε, sinh ra từ bộ chữ cái Σ.

2

●

∞

L* = ∪ L

Bao ñóng dương (positive):
+

Σ

+

Σ

i

+

i

Ø và {ε} cũng ñược coi là ngôn ngữ
Ø ≠ {ε} và {Ø} ≠ {ε}

thành lập một ngôn ngữ
bằng cách kết nối các chuỗi (với số lượng bất kỳ) các
chuỗi của một ngôn ngữ L cho trước
0

Một ngôn ngữ (hình thức) L là một
của các ký hiệu từ một bộ chữ cái Σ nào ñó.

7

L...
1
Khái niệm ngôn ngữ
Cách biểu diễn ngôn ngữ
Văn phạm
Sự phân lớp văn phạm
2
là một thực thể trừu tượng mà ta
không ñịnh nghĩa ñược một cách hình thức
Các chữ cái a, b, c … hoặc các số 1, 2, 3 …
Là một tập (không rng) các ký hiệu nào ñó
Bộ chữ cái Latin {A, B, C, …, a, b, c, , z}
một chuỗi (hay một từ - word) trên bộ
chữ cái Σ
Là một dãy hữu hạn các ký hiệu của Σ
Một ký hiệu có thể xuất hiện nhiều lần
3
là số các ký hiệu tạo thành chuỗi
abca = 4
ký hiệu , là chuỗi không có ký hiệu nào
|ε| = 0
chuỗi v là chuỗi con của w nếu v ñược tạo
bởi các ký hiệu liền kề nhau trong chuỗi w.
Chuỗi 10 là chuỗi con của chuỗi 0
001
là chuỗi con bất kỳ nằm ở ñầu chuỗi
là chuỗi con bất kỳ nằm ở cuối chuỗi
Chuỗi abc
có các tiền tố a, ab, abc
Chuỗi 0246
có các hậu tố 6, 46, 246, 0246
4
là chuỗi ñược tạo thành bằng
cách viết chuỗi thứ nhất, sau ñó viết chuỗi thứ hai, ...
Nối ghép của chuỗi Long
và Int là LongInt
Nối kết của chuỗi rỗng: εw = wε = w (với mọi w)
→ ε là ñơn vị của phép nối kết
của chuỗi w, ký hiệu w
R
, là chuỗi
w ñược viết theo thứ tự ngược lại.
w = abcd → w
R
= dcba ε
R
= ε
Printed with FinePrint - purchase at www.fineprint.com
Lý thuyết thông tin phần 2 - Trang 2
Lý thuyết thông tin phần 2 - Người đăng: Duy Khanh
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
5 Vietnamese
Lý thuyết thông tin phần 2 9 10 832