LÝ THUYẾT TÍNH TOÁN INTRODUCTION TO COMPUTATION THEORY (FORMAL LANGUAGES & AUTOMATA)

Bài 01. Tổng Quan

TIN331

GV: Nguyễn Ngọc Tú Tu.NguyenNgoc@hoasen.edu.vn

Khái niệm căn bản

 Ngôn ngữ (languages)  Văn phạm (grammar)  Ôtômát (automata)

Ngôn ngữ

 Ngôn ngữ là gì?

 Các từ điển định nghĩa ngôn ngữ một cách không chính xác là một hệ thống thích hợp cho việc biểu thị hay các khái niệm, bao các ý nghĩ, các sự kiện, gồm một tập các kí hiệu và các qui tắc để vận dụng chúng.

 Định nghĩa trên chưa đủ và chính xác xây dựng một định nghĩa toán học cho khái niệm ngôn ngữ

Ngoân Ngöõ

4

 Baûng chöõ caùi (Alphabet): Moät taäp khaùc roãng (troáng)

höõu haïn caùc kyù hieäu

 Chuoãi (String): daõy höõu haïn caùc kyù hieäu töø 

 = {a, b}

w = abaaa

: chuoãi roãng (empty string)

*: Taäp taát caû caùc chuoãi treân  (+ = *  {})

Ngoân Ngöõ

 Chuỗi (string), w

 Là một dãy hữu hạn các kí hiệu từ bảng chữ cái.

 Ví dụ

 Với Σ = {a, b}, thì abab và aaabbba là các chuỗi trên Σ.

 Qui ước

 Với một vài ngoại lệ, chúng ta sẽ sử dụng các chữ cái thường a, b, c, . . . cho các phần tử của Σ còn các chữ cái u, v, w, . . . Cho các tên chuỗi.

Ngoân Ngöõ

6

 Ngoân ngöõ: moät taäp con L cuûa *  Caâu: moät chuoãi trong L  Ví duï 1:

 = {a, b}

* = {, a, b, aa, ab, ba, bb, aaa, ...}

L1 = {a, aa, aab} (Ngoân ngöõ höõu haïn)

L2 = {anbn | n  0} = {, ab, aabb, ...}

Ngoân Ngöõ

 Kết nối (concatenation), wv

 w = a1a2 ...an và v = b1b2...bm là chuỗi: wv = a1a2 ...anb1b2...bm

 Ðảo (reverse), wR

 Ðảo của chuỗi w = a1a2 ...an là chuỗi: wR= an...a2a1

Ngoân Ngöõ

8

 Keát noái ngoân ngöõ (Language concatenation):

L1L2 = {xy | xL1, yL2}

Ln = L L ... L (n laàn)

 Ví duï 2:

L0 = {}

L = {anbn | n  0}  L2 = {anbnambm | n  0, m 

0}

Ngoân Ngöõ

Cho chuỗi w = uv

Tiếp đầu ngữ (prefix)

u được gọi là tiếp đầu ngữ của w

Tiếp vĩ ngữ (suffix)

v được gọi lá tiếp vĩ ngữ của w

Chiều dài của chuỗi w

Là số kí hiệu trong chuỗi, và được kí hiệu là |w|

Chuỗi trống (empty string)

Là chuỗi không có kí hiệu nào, thường được kí hiệu là 

Ngoân Ngöõ

10

 Bao đóng sao (Star-closure):

 L1  L2

...

 Bao đóng dương (Positive closure):

L* = L0

...

L+ = L1  L2

Ngôn ngữ

Ngôn ngữ

Là một tập con của Σ*, hay nói cách khác là một tập bất kỳ các câu trên bộ chữ cái.

Ví dụ

Cho Σ = {a, b}

Σ* = {λ, a, b, aa, ab, ba, bb, aaa, aab, ...} Tập {a, aa, aab} là một ngôn ngữ trên Σ. Nó là một ngôn ngữ hữu hạn. Tập L = {anbn : n ≥ 0} cũng là một ngôn ngữ trên Σ. Nó là một ngôn ngữ vô hạn.

Các phép toán trên ngôn ngữ

 Bù (complement), L

 Bù của ngôn ngữ L trên bảng chữ cái Σ, được kí hiệu là: L = Σ* - L  Kết nối, L1L2

 Cho 2 ngôn ngữ L1, L2. Kết nối của 2 ngôn ngữ L1, L2 là: L1L2= { xy : x ∈ L1, y ∈ L2 }

 Lũy thừa, Ln

 Lũy thừa bậc n của L, kí hiệu là Ln, là việc kết nối L với

chính nó n lần

L0 = { }

LL L = 1 2 3 L

nlaàn

Các phép toán trên ngôn ngữ

 Ví dụ

 Cho L = {anbn : n ≥ 0}, thì L2 = {anbnambm: n ≥ 0 , m ≥ 0}

 Bao đóng-sao (star-closure) của L  Kí hiệu là L* và được định nghĩa là L* = L0 ∪ L1∪ L2∪ ...

 Bao đóng dương (positive closure) của L

 Kí hiệu là L+ L+ = L1∪ L2∪ L3∪ ...

Vaên Phaïm

14

 Moät vaên phaïm (grammar) cuûa moät ngoân ngöõ töï nhieân (natural language) cho chuùng ta bieát moät caâu cuï theå coù ñöôïc caáu taïo toát hay khoâng.

 a | the

Các từ điển định nghĩa văn phạm một cách

 boy | dog

không chính xác là một tập các qui tắc về cấu

tạo từ và các qui tắc về cách liên kết các từ lại

 runs | walks

thành câu.

Văn phạm

Các câu “a boy runs” và “the dog walks” là có "dạng đúng“, tức là được sinh ra từ các luật của văn phạm. Định nghĩa 1.1

Văn phạm G được định nghĩa như là một bộ bốn

G = (V, T, S, P) V: tập các kí hiệu không kết thúc (nonterminal symbol), còn được gọi là các biến (variable), T: tập các kí hiệu kết thúc (terminal symbol), S ∈ V: được gọi là biến khởi đầu (start variable), đôi khi còn được gọi là kí hiệu mục tiêu, P: tập hữu hạn các luật sinh (production),

Văn phạm

16

 Vaên phaïm hình thöùc (Formal grammar):

G = (V, T, S, P)

T: taäp höõu haïn caùc kyù hieäu keát thuùc (terminal symbols)

V: taäp höõu haïn caùc bieán (variables)

SV: bieán khôûi ñaàu (start variable)

P: taäp höõu haïn caùc luaät sinh (productions)

Văn phạm

 Qui ước:

 Các kí tự chữ hoa A, B, C, D, E và S biểu thị các biến; S là

kí hiệu khởi đầu trừ phi được phát biểu khác đi.

 Các kí tự chữ thường a, b, c, d, e, các kí số, các chuỗi in

đậm biểu thị các kí hiệu kết thúc (terminal).

 Các kí tự chữ hoa X, Y, Z biểu thị các kí hiệu có thể là

terminal hoặc biến.

 Các kí tự chữ thường u, v, w, x, y, z biểu thị chuỗi các

terminal.

 Các kí tự chữ thường Hi Lạp α, β, γ biểu thị chuỗi các biến

và các terminal.

Vaên Phaïm

18

 Caùc luaät sinh:

x  y

 Chuoãi w = uxv daãn xuaát ra z = uyv

x(VT)+ y(VT)*

w  z (daãn xuaát tröïc tieáp)

w1 * wn (w1  w2  ...  wn | w1 = wn) w1 + wn (ít nhaát moät luaät sinh ñöôïc aùp duïng)

Vaên Phaïm

19

 Ngoân ngöõ ñöôïc sinh bôûi:

G = (V, T, S, P)

 Daãn xuaát caâu (derivation):

L(G) = {wT* | S * w} laø:

 Daïng caâu (sentential forms): S, w1, w2, ..., wn (chöùa

S  w1  w2  ...  wn  wL(G)

caùc bieán)

Vaên Phaïm

20

 Ví duï 3:

G = ({S}, {a, b}, S, P)

S  

S  aSb  aaSbb  aabb

aabb: caâu

aaSbb: daïng caâu

P: S  aSb

L(G) = {anbn | n  0}

Vaên Phaïm

21

 Ví duï 4:

G1 = ({A, S}, {a, b}, S, P1)

A  aAb | 

P1: S  aAb | 

G vaø G1 laø töông ñöông

L(G1) = {anbn | n  0}

Vaên Phaïm

22

 Ví duï 5:

G2 = ({S}, {a, b}, S, P2)

S  

P2: S  SS

S  aSb

S  bSa

L(G2) = {w | na(w) = nb(w)}

Automat

23

Moät moâ hình tröøu töôïng cuûa maùy tính soá:

Input file

Storage

Control unit

Output

Automat

24

Thiết bị đầu vào (input file): là nơi mà các chuỗi nhập (input string) được ghi lên, và được ôtômát đọc nhưng không thay đổi được nội dung của nó. Nó được chia thành các ô (cells, squares), mỗi ô giữ được một kí hiệu.

Cơ cấu nhập (input mechanism): là bộ phận có thể đọc input file từ trái sang phải, một kí tự tại một thời điểm. Nó cũng có thể dò tìm được điểm kết thúc của chuỗi nhập (eof, #). Bộ nhớ tạm (temporary storage): là thiết bị bao gồm một số không giới hạn các ô nhớ (cell), mỗi ô có thể giữ một kí hiệu từ một bảng chữ cái (không nhất thiết giống với bảng chữ cái ngõ nhập). Ôtômát có thể đọc và thay đổi được nội dung của các ô nhớ lưu trữ (storage cell).

Dựa vào hoạt động của ôtômát, có đơn định hay không: có hai loại ôtômát. Ôtômát đơn định (deterministic automata): là ôtômát trong

đó mỗi di chuyển (move) được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện tính đơn định.

Ôtômát không đơn định (non-deterministic automata): là

ôtômát mà tại mỗi thời điểm nó có một vài khả năng lựa chọn để di chuyển. Việc có một vài khả năng lựa chọn thể hiện tính không đơn định.

Dựa vào kết quả xuất ra của ôtômát: có hai loại ôtômát. Accepter: là ôtômát mà đáp ứng ở ngõ ra của nó được giới hạn trong hai trạng thái đơn giản “yes” hay “no”. "Yes" tương ứng với việc chấp nhận chuỗi nhập, "no" tương ứng với việc từ chối, không chấp nhận, chuỗi nhập.

Transducer: là ôtômát tổng quát hơn, có khả năng sinh ra các

chuỗi kí tự ở ngõ xuất. Máy tính số là một transducer điển hình.

VD

 Dùng văn phạm mô tả danh hiệu của Pascal.

,

| |  ,  a .. z | A .. Z  0 .. 9

VD

 Dùng accepter mô tả danh hiệu của Pascal

Letter

1

2

Digit

Letter or digit

3

Letter or digit

VD

Một văn phạm đơn giản của ngôn ngữ Pascal

[prog] ::= [prog header] [var part] [stat part] [prog header] ::= program [id] ( input , output ) ; [var part] ::= var [var dec list] [stat part] ::= begin [stat list] end .

[var dec list] ::= [var dec] | [var dec list] [var dec] [var dec] ::= [id list] : [type] ;

[stat list] ::= [stat] | [stat list] ; [stat] [stat] ::= [assign stat] [assign stat] ::= [id] := [expr]