Bài giảng Lý thuyết tính toán Chương 3: PGS.TS. Phan Huy Khánh

(Theory of Computation)

Lý thuy

Lý thuyế

ết t

t tí

ính to

nh toá

án

(Theory of Computation)

PGS.TS. Phan Huy Kh

PGS.TS. Phan Huy Khá

ánh

khanhph@vnn.vn

Chương 3

Văn phạm

và ôtômat đẩy xuống

Chương

Chương 3

Văn ph

Văn phạ

ạm

và

à ôtômat đ

ôtômat đẩ

ẩy x u

y x u ố

ống

2/2/ 7777

Chương

Chương 3

3 Văn ph

Văn phạ

ạm v

m và

à ôtômat đ

ôtômat đẩ

ẩy xu

y xuố

ống



Kh

Khá

ái ni

i niệ

ệm ngôn ng

m ngôn ngữ

ữl

lậ

ập tr

p trì

ình (N

nh (NNLT)

NLT)



Văn ph

Văn phạ

ạm

Kh

Khá

ái ni

i niệ

ệm văn ph

m văn phạ

ạm

Phân c

Phân cấ

ấp c

p cá

ác lo

c loạ

ại văn ph

i văn phạ

ạm c

m củ

ủa Chomsky

a Chomsky

Văn ph

Văn phạ

ạm ch

m chí

ính qui

nh qui



Ôtômat đ

Ôtômat đẩ

ẩy xu

y xuố

ống

Ngôn ng

Ngôn ngữ

ữphi ng

phi ngữ

ữc

cả

ảnh

Quan h

Quan hệ

ệv

vớ

ới c

i cá

ác ôtômat đ

c ôtômat đẩ

ẩy xu

y xuố

ống

T

Tí

ính ch

nh chấ

ất c

t củ

ủa c

a cá

ác ngôn ng

c ngôn ngữ

ữphi ng

phi ngữ

ữc

cả

ảnh

3/3/ 7777

Lị

ịch s

ch sử

ửngôn ng

ngôn ngữ

ữl

lậ

ập tr

p trì

ình



T

Từ

ừkhi m

khi má

áy t

y t í

ính đi

nh điệ

ện t

n tử

ửxu

xuấ

ất hi

t hiệ

ện,

n, con ngư

con ngườ

ời ph

i phả

ải t

i tì

ìm c

m cá

ách

lậ

ập tr

p trì

ình, hay l

nh, hay lậ

ập chương tr

p chương trì

ình (Programming)

nh (Programming)

Nh

Nhữ

ững ngôn ng

ng ngôn ngữ

ữ đ

đầ

ầu tiên ch

u tiên chỉ

ỉl

là

àt

tổ

ổh

hợ

ợp c

p củ

ủa c

a cá

ác con s

c con số

ố(bit) 0

(bit) 0

và

à1, g

1, gọ

ọi l

i là

àngôn ng

ngôn ngữ

ữm

má

áy (Machine Language)

y (Machine Language)

Ngôn ng

Ngôn ngữ

ữm

má

áy ph

y phụ

ụthu

thuộ

ộc ho

c hoà

àn to

n toà

àn v

n và

ào t

o tổ

ổch

chứ

ức ph

c phầ

ần c

n cứ

ứng

củ

ủa m

a má

áy, v

y, và

àr

rấ

ất sơ c

t sơ cấ

ấp

Vi

Việ

ệc l

c lậ

ập tr

p trì

ình r

nh rấ

ất kh

t khó

ó khăn

khăn, nh

, nhọ

ọc nh

c nhằ

ằn v

n và

àd

dễ

ễsai s

sai só

ót



T

Từ

ừnh

nhữ

ững năm

ng năm 1950,

1950, đ

để

ểgi

giả

ảm nh

m nhẹ

ẹvi

việ

ệc l

c lậ

ập tr

p trì

ình :

nh :

Ngư

Ngườ

ời ta

i ta s

sử

ửd

dụ

ụng

ng k

kỹ

ỹthu

thuậ

ật g

t gọ

ọi chương tr

i chương trì

ình con (Subprogram

nh con (Subprogram

hay Subroutine)

hay Subroutine) b

bằ

ằng c

ng cá

ách

ch d

dù

ùng

ng l

lạ

ại nh

i nhữ

ững chương tr

ng chương trì

ình đã vi

nh đã viế

ết

Ngư

Ngườ

ời ta xây d

i ta xây dự

ựng c

ng cá

ác thư vi

c thư việ

ện (

n (kho chương tr

kho chương trì

ình m

nh mẫ

ẫu)

u) đ

để

ể

khi c

khi cầ

ần th

n thì

ìg

gọ

ọi đ

i đế

ến

4/4/ 7777

Sự

ự ra đ

ra đờ

ời c

i củ

ủa h

a hợ

ợp ng

p ngữ

ữ



Ngôn ng

Ngôn ngữ

ữh

hợ

ợp d

p dị

ịch ra đ

ch ra đờ

ời t

i từ

ừnh

nhữ

ững năm

ng năm 1950 :

1950 :

G

Gọ

ọi t

i tắ

ắt h

t hợ

ợp ng

p ngữ

ữ (

(Assembly) hay còn

Assembly) hay còn đư

đượ

ợc g

c gọ

ọi l

i là

àc

cá

ác ngôn

c ngôn

ngữ

ữbi

biể

ểu tư

u tượ

ợng (Symbolic Language)

ng (Symbolic Language)

Trong h

Trong hợ

ợp ng

p ngữ

ữ, c

, cá

ác mã l

c mã lệ

ệnh v

nh và

à đ

đị

ịa ch

a chỉ

ỉc

cá

ác to

c toá

án h

n hạ

ạng đư

ng đượ

ợc

thay th

thay thế

ếb

bở

ởi c

i cá

ác t

c từ

ừti

tiế

ếng Anh g

ng Anh gợ

ợi nh

i nhớ

ớ (

(Mnemonic) n

Mnemonic) như DIV

hư DIV,

JUMP, MUL...



C

Cá

ác chương tr

c chương trì

ình vi

nh viế

ết b

t bằ

ằng Assembly :

ng Assembly :

Không th

Không thể

ểch

chạ

ạy ngay đư

y ngay đượ

ợc m

c mà

àph

phả

ải qua giai đo

i qua giai đoạ

ạn h

n hợ

ợp d

p dị

ịch

(Assembler) th

(Assembler) thà

ành ngôn ng

nh ngôn ngữ

ữm

má

áy

Ph

Phụ

ụthu

thuộ

ộc v

c và

ào ph

o phầ

ần c

n cứ

ứng

Xa l

Xa lạ

ạv

vớ

ới ngôn ng

i ngôn ngữ

ữt

tự

ựnhiên (Natural language)

nhiên (Natural language)

5/5/ 7777

Ngôn ng

Ngôn ngữ

ữm

má

áy ti

y tiế

ến g

n gầ

ần đ

n đế

ến ngôn ng

n ngôn ngữ

ữt

tự

ựnhiên

nhiên



Năm

Năm 1957 :

1957 :

FORTRAN (FORmula TRANslator/ biên d

FORTRAN (FORmula TRANslator/ biên dị

ịch c

ch cá

ác công th

c công thứ

ức)

đư

đượ

ợc IBM đ

c IBM đề

ề xư

xướ

ớng l

ng là

àm

mộ

ột trong nh

t trong nhữ

ững NNLT đ

ng NNLT đầ

ầu tiên

u tiên

FORTRAN g

FORTRAN gầ

ần g

n gũ

ũi ngôn ng

i ngôn ngữ

ữt

tự

ựnhiên v

nhiên vớ

ới c

i cá

ách di

ch diễ

ễn đ

n đạ

ạt

Toá

án h

n họ

ọc cho ph

c cho phé

ép gi

p giả

ải quy

i quyế

ết c

t cá

ác b

c bà

ài to

i toá

án khoa h

n khoa họ

ọc

c –

–

kỹ

ỹthu

thuậ

ật v

t và

à đư

đượ

ợc

c ứ

ứng d

ng dụ

ụng r

ng rấ

ất r

t rộ

ộng rãi

ng rãi

Ti

Tiế

ếp theo l

p theo là

às

sự

ự ra đ

ra đờ

ời c

i củ

ủa c

a cá

ác NNLT như

c NNLT như :

ALGOL 60 (ALGOrithmic Language) 1960,

ALGOL 60 (ALGOrithmic Language) 1960,

COBOL (Comon Business Orient ed Language) 1964

COBOL (Comon Business Oriented Language) 1964

Simula, v.v...

Simula, v.v...

6/6/ 7777

Phá

át tri

t triể

ển c

n củ

ủa NNLT

a NNLT



Theo s

Theo sự

ựph

phá

át tri

t triể

ển c

n củ

ủa c

a cá

ác th

c thế

ếh

hệ

ệm

má

áy t

y tí

ính, c

nh, cá

ác ngôn ng

c ngôn ngữ

ữ

lậ

ập tr

p trì

ình c

nh cũ

ũng không ng

ng không ngừ

ừng đư

ng đượ

ợc c

c cả

ải ti

i tiế

ến v

n và

àho

hoà

àn thi

n thiệ

ện đ

n để

ể

cà

àng ng

ng ngà

ày c

y cà

àng đ

ng đá

áp

p ứ

ứng nhu c

ng nhu cầ

ầu c

u củ

ủa ngư

a ngườ

ời s

i sử

ửd

dụ

ụng v

ng và

giả

ảm nh

m nhẹ

ẹcông vi

công việ

ệc l

c lậ

ập tr

p trì

ình



Nhi

Nhiề

ều ngôn ng

u ngôn ngữ

ữ đã ra đ

đã ra đờ

ời v

i và

àh

hì

ình th

nh thà

ành hai lo

nh hai loạ

ại ngôn ng

i ngôn ngữ

ữ:



Ngôn ng

Ngôn ngữ

ữm

má

áy b

y bậ

ậc th

c thấ

ấp (low

p (low-

-level language)

level language)



H

Hợ

ợp ng

p ngữ

ữ



Ngôn ng

Ngôn ngữ

ữl

lậ

ập tr

p trì

ình b

nh bậ

ậc cao

c cao



C

Cá

ác ngôn ng

c ngôn ngữ

ữb

bậ

ậc th

c thấ

ấp v

p và

àh

hợ

ợp ng

p ngữ

ữ, t

, thư

hườ

ờng ch

ng chỉ

ỉd

dù

ùng đ

ng để

ể

viế

ết c

t cá

ác tr

c trì

ình đi

nh điề

ều khi

u khiể

ển v

n và

àki

kiể

ểm tra thi

m tra thiế

ết b

t bị

ị,

cá

ác tr

c trì

ình s

nh sử

ửa l

a lỗ

ỗi (Debugger)...

i (Debugger)...

7/7/ 7777

Ngôn ng

Ngôn ngữ

ữl

lậ

ập tr

p trì

ình b

nh bậ

ậc cao

c cao



C

Cá

ác ngôn ng

c ngôn ngữ

ữl

lậ

ập tr

p trì

ình b

nh bậ

ậc cao (High

c cao (High-

-level Language) :

level Language) :

Công c

Công cụ

ụgi

giú

úp gi

p giả

ải quy

i quyế

ết c

t cá

ác v

c vấ

ấn đ

n đề

ềth

thự

ực t

c tế

ế

L

Là

à nơi m

nơi mà

ành

nhữ

ững th

ng thà

ành t

nh tự

ựu nghiên c

u nghiên cứ

ứu m

u mớ

ới nh

i nhấ

ất c

t củ

ủa Tin h

a Tin họ

ọc

đư

đượ

ợc đưa v

c đưa và

ào

L

Lĩ

ĩnh v

nh vự

ực nghiên c

c nghiên cứ

ứu ph

u phá

át tri

t triể

ển c

n cá

ác ngôn ng

c ngôn ngữ

ữl

lậ

ập tr

p trì

ình v

nh vừ

ừa c

a có

tí

ính truy

nh truyề

ền th

n thố

ống, v

ng, vừ

ừa c

a có

ót

tí

ính hi

nh hiệ

ện đ

n đạ

ại

8/8/ 7777

Rấ

ất nhi

t nhiề

ều NNLT b

u NNLT bậ

ậc cao đã đư

c cao đã đượ

ợc ph

c phá

át tri

t triể

ển

Mộ

ột v

t và

ài NNLT quen thu

i NNLT quen thuộ

ộc :

c :

Lisp (LISt Processing)

Lisp (LISt Processing) 1960

1960

PL/1 (Programming Language number 1)

PL/1 (Programming Language number 1) 1963

1963

Basic (Beginner

Basic (Beginner’

’s All

s All-

-Purpose Symbolic I nstruction Code) 1964

Purpose Symbolic I nstruction Code) 1964

Pascal (l

Pascal (lấ

ấy tên nh

y tên nhà

àTo

Toá

án h

n họ

ọc Ph

c Phá

áp Blaise PASCAL)

p Blaise PASCAL) 1970

1970

PROLOG (PROgramming in LOGic)

PROLOG (PROgramming in LOGic) 1970

1970

C

C1972

1972

ADA (l

ADA (lấ

ấy tên nh

y tên nhà

àn

nữ

ữkhoa h

khoa họ

ọc Augusta Ada Byron)

c Augusta Ada Byron) 1980

1980

C+ + ,

C+ + , Java, C# ,

Java, C# , Visual Basic

Visual Basic

Cơ s

Cơ sở

ởD

Dữ

ữli

liệ

ệu, l

u, lậ

ập tr

p trì

ình h

nh hà

àm, l

m, lậ

ập tr

p trì

ình logic,

nh logic, hư

hướ

ớng đ

ng đố

ối tư

i tượ

ợng,

ng,

v.v...

9/9/ 7777

Phân lo

Phân loạ

ại NNLT theo phương th

i NNLT theo phương thứ

ức



C

Có

ónhi

nhiề

ều NNLT theo phương th

u NNLT theo phương thứ

ức :

c :

M

ệ

nh l

ệ

nh (imperative) : Fortran (1957), Cobol (1959), Basic

(imperative) : Fortran (1957), Cobol (1959), Basic

(1965), Pascal (1970), C (1971), Ada (1979)...



Đị

ịnh hư

nh hướ

ớng đ

ng đố

ối tư

i tượ

ợ

ng (object

(object-

-oriented)

oriented) : Smallt alk (1969), C+ +

: Smallt alk (1969), C+ +

(1983), Eiffel (1986), Java (1991), C# (2000), ...

H

Hà

àm

m(functional) : Lisp (1958)

(functional) : Lisp (1958),

, ML (1973), Scheme (1975),

ML (1973), Scheme (1975),

Caml (1987), Miranda (1982), ...

Logic

Logic (logic

(logic-

-based) ch

based) chủ

ủy

yế

ếu l

u là

àngôn ng

ngôn ngữ

ữProlog (1970)

Prolog (1970)

Ngôn ng

Ngôn ngữ

ữthao t

thao tá

ác cơ s

c cơ sở

ởd

dữ

ữli

liệ

ệu như SQL

u như SQL (1980)...

(1980)...

X

Xử

ửlý

lý song song

song song (parallel) : Ada, Occam (1982), C

(parallel) : Ada, Occam (1982), C-

-Linda, ...

Linda, ...



Ngo

Ngoà

ài ra còn c

i ra còn có

ó:

L

ậ

p tr

p trì

ình phân b

nh phân b

ổ

(Distributed Programming).

L

ậ

p tr

p trì

ình r

nh rà

àng bu

ng bu

ộ

c(Constraint Programming).

(Constraint Programming).

L

ậ

p tr

p trì

nh hư

nh hướ

ớ

ng truy c

ậ

p(Access

(Access-

-Oriented Programming).

Oriented Programming).

L

ậ

p tr

p trì

ình theo lu

nh theo lu

ồ

ng d

ữ

ệ

u(Dataflow Programming), v.v...

(Dataflow Programming), v.v... 10/10/ 7777

Đị

ịnh ngh

nh nghĩ

ĩa m

a mộ

ột NNLT b

t NNLT bậ

ậc cao

c cao



M

Mộ

ột NNLT b

t NNLT bậ

ậc cao đư

c cao đượ

ợc xây d

c xây dự

ựng mô ph

ng mô phỏ

ỏng

(mộ

ột c

t cá

ách thô thi

ch thô thiể

ển) ngôn ng

n) ngôn ngữ

ữt

tự

ự nhiên

nhiên,

thư

thườ

ờng l

ng là

àti

tiế

ếng Anh (ho

ng Anh (hoặ

ặc ti

c tiế

ếng Nga), t

ng Nga), t ừ

ừb

bố

ốn y

n yế

ếu t

u tố

ố:

B

Bộ

ộký t

ký tự

ự(Character Set)

(Character Set)

B

Bộ

ột

từ

ừv

vự

ựng (Vocabulary)

ng (Vocabulary)

C

Cú

úph

phá

áp (Semantic)

p (Semantic)

Ng

Ngữ

ữngh

nghĩ

ĩa (Semantic)

a (Semantic)

Căn c

Căn cứ

ứv

và

ào c

o cú

úph

phá

áp c

p củ

ủa NNLT,

a NNLT, ngư

ngườ

ời l

i lậ

ập tr

p trì

ình vi

nh viế

ết chương tr

t chương trì

ình

gồ

ồm c

m cá

ác câu l

c câu lệ

ệnh đ

nh để

ểgi

giả

ải quy

i quyế

ết b

t bà

ài to

i toá

án c

n củ

ủa m

a mì

ình

M

Mỗ

ỗi câu l

i câu lệ

ệnh vi

nh viế

ết ra không nh

t ra không nhữ

ững đ

ng đú

úng đ

ng đắ

ắn v

n về

ềm

mặ

ặt c

t cú

úph

phá

áp,

mà

àcòn ph

còn phả

ải đ

i đú

úng đ

ng đắ

ắn c

n cả

ảv

về

ềm

mặ

ặt ng

t ngữ

ữngh

nghĩ

ĩa, hay ý ngh

a, hay ý nghĩ

ĩa logic

a logic

củ

ủa câu l

a câu lệ

ệnh,

nh, đ

để

ểgi

giả

ải quy

i quyế

ết b

t bà

ài to

i toá

án



Ngo

Ngoà

ài ra, còn c

i ra, còn có

óy

yế

ếu t

u t ố

ốm

mộ

ột th

t thứ

ứ năm l

năm là

àt

tí

ính th

nh thự

ực d

c dụ

ụng

(Pragmatic)

11/11/ 7777

Bộ

ộký t

ký tự

ự



B

Bộ

ộký t

ký t ự

ự(Character Set)

(Character Set)

G

Gồ

ồm m

m mộ

ột t

t tậ

ập h

p hợ

ợp h

p hữ

ữu h

u hạ

ạn c

n cá

ác ký t

c ký tự

ự

đư

đượ

ợc ph

c phé

ép d

p dù

ùng trong ngôn ng

ng trong ngôn ngữ

ữ, t

, thư

hườ

ờng l

ng là

àc

cá

ác ký t

c ký tự

ựASCII

ASCII

C

Có

óth

thể

ểhi

hiể

ểu b

u bộ

ộký t

ký tự

ực

có

ó vai trò như b

vai trò như bả

ảng ch

ng chữ

ữc

cá

ái (Alphabet)

i (Alphabet)

củ

ủa m

a mộ

ột ngôn ng

t ngôn ngữ

ữt

tự

ựnhiên

nhiên



V

Ví

íd

dụ

ụb

bộ

ộ9 n

9 né

ét cơ b

t cơ bả

ản d

n dù

ùng vi

ng viế

ết ch

t chữ

ữH

Há

án :

n :

12/12/ 7777

Bộ

ột

từ

ừv

vự

ựng



B

Bộ

ột

từ

ừv

vự

ựng (Vocabulary)

ng (Vocabulary)

G

Gồ

ồm c

m cá

ác t

c t ừ

ừ (

(Word) hay

Word) hay đơn v

đơn vị

ịt

từ

ừv

vự

ựng (Token) d

ng (Token) dù

ùng đ

ng để

ểt

tạ

ạo th

o thà

ành

câu l

câu lệ

ệnh v

nh và

à đư

đượ

ợc phân lo

c phân loạ

ại tu

i tuỳ

ỳtheo vai trò c

theo vai trò củ

ủa ch

a chú

úng trong NNLT

ng trong NNLT

M

Mỗ

ỗi lo

i loạ

ại t

i từ

ừv

vự

ựng l

ng lạ

ại đư

i đượ

ợc chia ra th

c chia ra thà

ành c

nh cá

ác nh

c nhó

óm nh

m nhỏ

ỏ hơn

hơn

tuỳ

ỳtheo ch

theo chứ

ức năng s

c năng sử

ửd

dụ

ụng



V

Ví

íd

dụ

ụ:

- Tên, hay định danh (Ident ifier) :

Read, Write, P, x, y

- Hằng (Constants) : 2

- Toán tử(Operators) : + , :=

- Dấu phân cách (Delimiters) :

:, (, ), Begin, End.

- Từkhoá/dành riêng (KeyWord) :

Program, Var, If Then...

Program P;

Var , y : Integer;

Begin

Read(x);

y:= x+ 2;

Write(y)

End.

Các đơn vịtừvựngChương trình Pascal

13/13/ 7777

Cú

úph

phá

áp



C

Cú

úph

phá

áp (

p (Syntax) hay

Syntax) hay văn ph

văn phạ

ạm (Grammar)

m (Grammar)

là

àt

tậ

ập h

p hợ

ợp c

p cá

ác quy t

c quy tắ

ắc cho ph

c cho phé

ép :

p :

Quy đ

Quy đị

ịnh c

nh cá

ách th

ch thứ

ức k

c kế

ết h

t hợ

ợp c

p cá

ác ký t

c ký tự

ựth

thà

ành t

nh từ

ừ, k

, kế

ết h

t hợ

ợp c

p cá

ác

từ

ừth

thà

ành câu l

nh câu lệ

ệnh đ

nh đú

úng (Statement

ng (Statement -

-Instruction), k

Instruction), kế

ết h

t hợ

ợp

cá

ác câu l

c câu lệ

ệnh đ

nh đú

úng th

ng thà

ành m

nh mộ

ột chương tr

t chương trì

ình ho

nh hoà

àn ch

n chỉ

ỉnh

C

Có

óth

thể

ểh

hì

ình dung c

nh dung cá

ách k

ch kế

ết h

t hợ

ợp n

p nà

ày gi

y giố

ống c

ng cá

ách đ

ch đặ

ặt câu trong

t câu trong

mộ

ột ngôn ng

t ngôn ngữ

ữt

tự

ự nhiên

nhiên

Đ

Để

ể đ

đị

ịnh ngh

nh nghĩ

ĩa c

a cú

úph

phá

áp m

p mộ

ột ngôn ng

t ngôn ngữ

ữl

lậ

ập tr

p trì

ình, n

nh, ngư

gườ

ời ta

i ta

thư

thườ

ờng s

ng sử

ửd

dụ

ụng :

ng :

Ho

Hoặ

ặc sơ đ

c sơ đồ

ồc

cú

úph

phá

áp (Syntax Diagram)

p (Syntax Diagram)

Ho

Hoặ

ặc

c d

dạ

ạng chu

ng chuẩ

ẩn Backus

n Backus-

-Naur

Naur (BNF

(BNF

BackusNaur Normal Form),

BackusNaur Normal Form),

hay

hay d

dạ

ạng Backus

ng Backus-

-Naur m

Naur mở

ởr

rộ

ộng

ng (EBNF

(EBNF

Extended BNF)

Extended BNF)

14/14/ 7777

Ví

íd

dụ

ụ văn ph

văn phạ

ạm ti

m tiế

ếng Anh

ng Anh



Gi

Giả

ảs

sử

ửc

cá

ác câu t i

c câu t iế

ếng Anh đư

ng Anh đượ

ợc xây d

c xây dự

ựng theo nh

ng theo nhữ

ững quy

ng quy

tắ

ắc như sau

c như sau :

Câu

Câu (Phrase/Sentence) g

(Phrase/Sentence) gồ

ồm c

m có

óhai th

hai thà

ành ph

nh phầ

ần l

n lầ

ần lư

n lượ

ợt :

t :

Ch

ủ

ừ

(Subject)



Độ

ộ

ng t

ừ

(Verbe)

Ch

ủ

ừ

có

óth

thể

ểl

là

àHe

He ho

hoặ

ặc

c She

She



Độ

ộ

ng t

ừ

có

óth

thể

ểl

là

àsleep

sleep hay

hay eat

eat

T

Từ

ừ đ

đó

óc

có

óth

thể

ểxây d

xây dự

ựng đư

ng đượ

ợc c

c cá

ác câu ki

c câu kiể

ểu S+ V :

u S+ V :

He sleep

He sleep

He eat

He eat

She sleep

She sleep

She eat

She eat

15/15/ 7777

Ví

íd

dụ

ụ sơ đ

sơ đồ

ồc

cú

úph

phá

áp câu ti

p câu tiế

ếng Anh

ng Anh



Trong ti

Trong tiế

ếng Anh, m

ng Anh, mộ

ột câu đơn gi

t câu đơn giả

ản g

n gồ

ồm 3 th

m 3 thà

ành ph

nh phầ

ần :

n :

Ch

Chủ

ủt

từ

ừ(Subject), ch

(Subject), chẳ

ẳng h

ng hạ

ạn

n “

“I

I”

”v

và

à“

“You

You”

”

Đ

Độ

ộng t

ng từ

ừ(Verb), ch

(Verb), chẳ

ẳng h

ng hạ

ạn

n “

“like

like”

”v

và

à“

“see

see”

”

B

Bổ

ổng

ngữ

ữ(Complement), ch

(Complement), chẳ

ẳng h

ng hạ

ạn

n “

“him

him”

”v

và

à“

“her

her”

”



D

Dù

ùng sơ đ

ng sơ đồ

ồc

cú

úph

phá

áp, ta c

p, ta có

ó:



T

Từ

ừ đ

đó

óc

có

óth

thể

ểxây d

xây dự

ựng c

ng cá

ác câu đ

c câu đú

úng :

ng :

“

“I see him

I see him”

”,

, “

“I like her

I like her”

”, v.v...

, v.v...

câu bổngữ

bổngữ

động từ

chủtừ

chủtừI

You động từlike

see

bổngữhim

her

16/16/ 7777

Khá

ái ni

i niệ

ệm BNF

m BNF



BNF g

BNF gồ

ồm m

m m ộ

ột dãy c

t dãy cá

ác quy t

c quy tắ

ắc, hay d

c, hay dạ

ạng th

ng thứ

ức

M

Mỗ

ỗi quy t

i quy tắ

ắc c

c có

ód

dạ

ạng : <

ng : < V

ế

trá

ái

i > ::= <

> ::= < V

ế

ả

i >

<

ế

trá

ái

i> t

> thư

hườ

ờng l

ng là

àm

mộ

ột ký hi

t ký hiệ

ệu ph

u phả

ải đư

i đượ

ợc đ

c đị

ịnh ngh

nh nghĩ

ĩa rõ

a rõ

<

ế

ả

i> l

> là

àm

mộ

ột dãy ký hi

t dãy ký hiệ

ệu, ho

u, hoặ

ặc đã đư

c đã đượ

ợc th

c thừ

ừa nh

a nhậ

ận,

hoặ

ặc đã đư

c đã đượ

ợc đ

c đị

ịnh ngh

nh nghĩ

ĩa trư

a trướ

ớc đ

c đó

ó, tuân theo m

, tuân theo mộ

ột quy ư

t quy ướ

ớc

nà

ào đ

o đó

D

Dấ

ấu ::= (ho

u ::= (hoặ

ặc

c 

,

,ho

hoặ

ặc =

c = )

) đ

đọ

ọc

c “

“

đư

đượ

ợc đ

c đị

ị

nh ngh

a l

a là

à”

”

N

Nế

ếu

có

ónhi

nhiề

ều v

u vế

ếph

phả

ải c

i cù

ùng đ

ng đị

ịnh ngh

nh nghĩ

ĩa m

a mộ

ột v

t vế

ếtr

trá

ái,

i, ngư

ngườ

ời ta

i ta

sử

ửd

dụ

ụng d

ng dấ

ấu |

u | đ

để

ểphân c

phân cá

ách theo ngh

ch theo nghĩ

ĩa lo

a loạ

ại tr

i trừ

ừ

D

Dạ

ạng BNF m

ng BNF mở

ởr

rộ

ộng s

ng sử

ửd

dụ

ụng hai c

ng hai cặ

ặp d

p dấ

ấu quy ư

u quy ướ

ớc :

c :

{...} : v

{...} : vế

ếph

phả

ải c

i có

óm

mộ

ột chu

t chuỗ

ỗi t

i t ừ

ừ 0

0 đ

đế

ến nhi

n nhiề

ều m

u mụ

ục li

c liệ

ệt kê < ...> *

t kê < ...> *

[...] : v

[...] : vế

ếph

phả

ải c

i có

ó0 ho

0 hoặ

ặc c

c có

ó1 m

1 mụ

ục li

c liệ

ệt kê (option)

t kê (option)

17/17/ 7777

Ví

íd

dụ

ụd

dạ

ạng BNF

ng BNF



D

Dạ

ạng BNF c

ng BNF cá

ác câu ti

c câu tiế

ếng Anh đơn gi

ng Anh đơn giả

ản như sau

n như sau :

< Câu> ::=

< Câu> ::= < Ch

< Chủ

ủt

từ

ừ > <

> < Đ

Độ

ộng t

ng từ

ừ> |

> |

< Ch

< Chủ

ủt

từ

ừ > <

> < Đ

Độ

ộng t

ng từ

ừ> < B

> < Bổ

ổng

ngữ

ữ>

< Ch

< Chủ

ủt

từ

ừ> ::=

> ::= “

“I

I”

”|

| “

“You

You”

”

<Đ

Độ

ộng t

ng từ

ừ> ::=

> ::= “

“like

like”

”|

| “

“see

see”

”

< B

< Bổ

ổng

ngữ

ữ> ::=

> ::= “

“him

him”

”|

| “

“her

her”

”



V

Ví

íd

dụ

ụ: tên trong ngôn ng

: tên trong ngôn ngữ

ữPascal :

Pascal :

< tên> = < ch

< tên> = < chữ

ữ> { < ch

> { < chữ

ữ> | < s

> | < số

ố> }

> }

Hoặ

ặc đ

c đị

ịnh ngh

nh nghĩ

ĩa đ

a đệ

ệquy :

quy :

< tên> = < ch

< tên> = < chữ

ữ> | < tên> < ch

> | < tên> < chữ

ữ> | < tên> < s

> | < tên> < số

ố>

< ch

< chữ

ữ>

= ‘

‘A

A’

’| ... |

| ... | ‘

‘Z

Z’

’|

| ‘

‘a

a’

’| ... |

| ... | ‘

‘z

z’

’

< s

< số

ố>

= ‘

‘0

0’

’| ... |

| ... | ‘

‘9

9’

’

18/18/ 7777

Sơ đ

Sơ đồ

ồc

cú

úph

phá

áp c

p củ

ủa tên

a tên



Tên trong ngôn ng

Tên trong ngôn ngữ

ữPascal c

Pascal có

ó sơ đ

sơ đồ

ồc

cú

úph

phá

áp như sau

p như sau :



V

Ví

íd

dụ

ục

cá

ác tên vi

c tên viế

ết đ

t đú

úng trong Pascal :

ng trong Pascal :

Delta, x1, x2, Read, v.v...

Delta, x1, x2, Read, v.v...



Tr

Trá

ái l

i lạ

ại, c

i, cá

ác chu

c chuỗ

ỗi ký t

i ký t ự

ự sau đây đ

sau đây đề

ều không ph

u không phả

ải l

i là

àtên :

tên :

1A

1A,

, 

,

, 

,

, b

bá

án

kí

ính

nh, v.v...

, v.v...

Tên Chữ

Chữ

Số

Chữ

A Z

... a z

...

Chữ

0 9

...

Số

19/19/ 7777

Ví

íd

dụ

ụm

mộ

ột NNLT đơn gi

t NNLT đơn giả

ản



Văn ph

Văn phạ

ạm c

m củ

ủa m

a mộ

ột NNLT đơn gi

t NNLT đơn giả

ản d

n dạ

ạng EBNF như sau

ng EBNF như sau :

< program>

< program> ::=

::= program

program < statement>

< statement> **end

end

< statement>

< statement> ::= < assignment> | < loop>

::= < assignment> | < loop>

< assignment>

< assignment> ::= < identifier> := < expression> ;

::= < identifier> := < expression> ;

< loop>

< loop> :=

:= while

while < expression>

< expression> do

do < statement>

< statement> ++done

done

< expression>

< expression> ::= < value>

::= < value>

| < value> + < value> | < value> < = < value>

< value>

< value> ::= < identifier> | < number>

::= < identifier> | < number>

< identifier>

< identifier> ::= < letter>

::= < letter>

| < identifier> < letter> | < identifier> < digit>

< letter>

< letter> ::=

::= ‘

‘A

A’

’| ... |

| ... | ‘

‘Z

Z’

’|

| ‘

‘a

a’

’| ... |

| ... | ‘

‘z

z’

’

< digit>

< digit> ::=

::= ‘

‘0

0’

’| ...

| ... |

| ‘

‘9

9’

’

< number>

< number> ::= < digit> | < number> < digit>

::= < digit> | < number> < digit>

20/20/ 7777

Lậ

ập tr

p trì

ình theo c

nh theo cú

úph

phá

áp văn ph

p văn phạ

ạm

Mộ

ột câu, t

t câu, tứ

ức l

c là

àm

mộ

ột chương tr

t chương trì

ình đơn gi

nh đơn giả

ản, ch

n, chẳ

ẳng h

ng hạ

ạn :

n :

program program n := 1 ; n := 1 ; w hilewhile n < = 10 n < = 10 dodo n := n + 1 ; n := n + 1 ; done enddone end

đư

đượ

ợc s

c sả

ản sinh t

n sinh t ừ

ừ văn ph

văn phạ

ạm đã cho nh

m đã cho nhờ

ờá

áp d

p dụ

ụng c

ng cú

úphphááp văn php văn phạạm m như sau

như sau :

< program> =

< program> = program

program < statement> *

< statement> * end

end

program

program < statement> < statement>

< statement> < statement> end

end

program

program < assignment> < loop>

< assignment> < loop> end

end

program

program < identifier> : = < expression> ;

< identifier> : = < expression> ;

while

while < expression>

< expression> do

do < statement > +

< statement> + done end

done end

program

program n : = < value> ;

n : = < value> ;

while

while < value> < = < value>

< value> < = < value> do

do < statement>

< statement> done

done end

end

program

program n : = < number> ;

n : = < number> ;

while

while < identif ier> < = < number>

< identifier> < = < number> do

do < assignment>

< assignment> done end

done end

program

program n : = 1 ;

n : = 1 ; w hile

while n < = 10

n < = 10 do

do < ident ifier> := < expression> ;

< identifier> := < expression> ; done

done

end

program

program n : = 1 ;

n : = 1 ; w hile

while n < = 10

n < = 10 do

do n := < value> + < value> ;

n : = < value> + < value> ; done end

done end

program

program n : = 1 ;

n : = 1 ;

while

while n < = 10

n < = 10 do

do n := < identifier > + < number> ;

n : = < identifier> + < number> ; done end

done end

program

program n : = 1 ;

n : = 1 ; w hile

while n < = 10

n < = 10 do

do n := n + 1 ;

n : = n + 1 ; done end

done end

21/21/ 7777

Quan ni

Quan niệ

ệm m

m mộ

ột chương tr

t chương trì

ình

nh l

là

àcâu

câu

Có

óth

thể

ể xem chương tr

xem chương trì

ình v

nh vừ

ừa r

a rồ

ồi như l

i như là

àm

mộ

ột câu trên m

t câu trên mộ

ột b

t bả

ảng

chữ

ữtu

tuỳ

ỳý, ch

ý, chẳ

ẳng h

ng hạ

ạn :

n :

program

program n : = 1 ;

n : = 1 ; while

while n < = 10

n < = 10 do

do n := n + 1 ;

n := n + 1 ; done end

done end

22/22/ 7777

Nhậ

ận x

n xé

ét



Ta đã l

Ta đã là

àm quen v

m quen vớ

ới hai phương ph

i hai phương phá

áp :

p :

S

Sử

ửd

dụ

ụng văn ph

ng văn phạ

ạm đ

m để

ểl

lậ

ập tr

p trì

ình (t

nh (tạ

ạo ra câu c

o ra câu củ

ủa ngôn ng

a ngôn ngữ

ữ)

)

và

àm

mộ

ột tr

t trì

ình biên d

nh biên dị

ịch đ

ch để

ểphân t

phân tí

ích c

ch cú

úph

phá

áp,

biên d

biên dị

ịch th

ch thà

ành tr

nh trì

ình kh

nh khả

ảthi

thi

S

Sử

ửd

dụ

ụng ôtôm

ng ôtômá

át đ

t để

ểphân t

phân tí

ích m

ch mộ

ột câu c

t câu củ

ủa ngôn ng

a ngôn ngữ

ữ

và

àth

thừ

ừa nh

a nhậ

ận câu khi qu

n câu khi quá

átr

trì

ình đo

nh đoá

án nh

n nhậ

ận l

n là

àth

thà

ành công

nh công



Hai phương ph

Hai phương phá

áp n

p nà

ày b

y bổ

ổsung cho nhau v

sung cho nhau và

à thông thư

thông thườ

ờng,

ng,

ngư

ngườ

ời ta s

i ta sử

ửd

dụ

ụng c

ng cả

ảhai d

hai dạ

ạng th

ng thứ

ức

c văn ph

văn phạ

ạm

m v

và

àôtôm

ôtômá

át

C

Có

ós

sự

ự tương

tương ứ

ứng gi

ng giữ

ữa mô t

a mô tả

ảs

sả

ản sinh v

n sinh và

àmô t

mô t ả

ảphân t

phân t í

ích,

ch,

ngh

nghĩ

ĩa l

a là

àc

có

óth

thể

ểbi

biế

ến đ

n đổ

ổi m

i mộ

ột mô t

t mô tả

ảphân t

phân t í

ích (m

ch (mộ

ột ôtôm

t ôtômá

át h

t hữ

ữu h

u hạ

ạn)

thà

ành m

nh mộ

ột mô t

t mô tả

ảs

sả

ản sinh v

n sinh và

à ngư

ngượ

ợc l

c lạ

ại

Lý thuy

Lý thuyế

ết NN h

t NN hì

ình th

nh thứ

ức chưa mô t

c chưa mô tả

ả đ

đầ

ầy đ

y đủ

ủc

cá

ác NN t

c NN tự

ựnhiên

nhiên

(ti

(tiế

ếng Anh, ti

ng Anh, tiế

ếng Ph

ng Phá

áp, ti

p, tiế

ếng Vi

ng Việ

ệt...)

t...) nhưng mô t

nhưng mô tả

ảv

và

àphân t

phân t í

ích

đầ

ầy đ

y đủ

ủc

cá

ác NNLT v

c NNLT và

à đư

đượ

ợc

c á

áp d

p dụ

ụng r

ng rộ

ộng rãi trong Tin h

ng rãi trong Tin họ

ọc

23/23/ 7777

Hoạ

ạt đ

t độ

ộng c

ng củ

ủa văn ph

a văn phạ

ạm



C

Cá

ác quy t

c quy tắ

ắc đ

c để

ểs

sả

ản sinh câu trên m

n sinh câu trên mộ

ột b

t bả

ảng ch

ng chữ

ữ

 đã cho còn

đã cho còn

đư

đượ

ợc g

c gọ

ọi l

i là

àvăn ph

văn phạ

ạm

mhay

hay quy t

quy t

ắ

c vi

ế

t l

ạ

i(Rewriting Rules)

(Rewriting Rules)

M

Mỗ

ỗi quy t

i quy tắ

ắc ch

c chỉ

ỉra m

ra mộ

ột dãy c

t dãy cá

ác ký hi

c ký hiệ

ệu (Symbols)

u (Symbols)

có

óth

thể

ể đư

đượ

ợc thay th

c thay thế

ếb

bở

ởi m

i mộ

ột dãy c

t dãy cá

ác ký hi

c ký hiệ

ệu kh

u khá

ác

Nh

Nhữ

ững ký hi

ng ký hiệ

ệu c

u có

óth

thể

ể đư

đượ

ợc thay th

c thay thế

ếb

bở

ởi m

i mộ

ột dãy

t dãy

cá

ác ký hi

c ký hiệ

ệu kh

u khá

ác đgl c

c đgl cá

ác

c ký hi

ký hiệ

ệu s

u sả

ản sinh,

n sinh, hay

hay chưa k

chưa kế

ết th

t thú

úc



Đ

Để

ểnh

nhậ

ận đư

n đượ

ợc m

c mộ

ột câu n

t câu nà

ào đ

o đó

ó, n

, ngư

gườ

ời ta ti

i ta tiế

ến h

n hà

ành như sau

nh như sau :

Xu

Xuấ

ất ph

t phá

át t

t từ

ừm

mộ

ột ký t

t ký t ự

ự đ

đặ

ặc bi

c biệ

ệt, g

t, gọ

ọi l

i là

àký t

ký tự

ự đ

đầ

ầu

u(Start Symbol),

(Start Symbol),

rồ

ồi

i á

áp d

p dụ

ụng l

ng lầ

ần lư

n lượ

ợt c

t cá

ác quy t

c quy tắ

ắc c

c củ

ủa văn ph

a văn phạ

ạm

Khi không còn c

Khi không còn có

óth

thể

ểthay th

thay thế

ếc

cá

ác ký hi

c ký hiệ

ệu b

u bở

ởi c

i cá

ác quy t

c quy tắ

ắc c

c củ

ủa

văn ph

văn phạ

ạm, ta nh

m, ta nhậ

ận đư

n đượ

ợc câu ch

c câu chỉ

ỉg

gồ

ồm nh

m nhữ

ững ký hi

ng ký hiệ

ệu c

u củ

ủa

a 

 đã

đã

cho, cò

cho, còn đgl

n đgl c

cá

ác ký hi

c ký hiệ

ệu k

u kế

ết th

t thú

úc

24/24/ 7777

Đị

ịnh ngh

nh nghĩ

ĩa h

a hì

ình th

nh thứ

ức văn ph

c văn phạ

ạm



M

Mộ

ột văn ph

t văn phạ

ạm l

m là

àm

mộ

ột b

t bộ

ộb

bố

ốn G = (N,

n G = (N, 

, R

, R, S

, S) t

) t rong đ

rong đó

ó:

N l

N là

àt

tậ

ập h

p hợ

ợp h

p hữ

ữu h

u hạ

ạn c

n cá

ác ký t

c ký tự

ựkhông k

không kế

ết th

t thú

úc (

c (Non

Non-

-Terminal

Terminal

Symbols)

N còn đư

N còn đượ

ợc g

c gọ

ọi l

i là

àc

cá

ác bi

c biế

ến, ch

n, chỉ

ỉxu

xuấ

ất hi

t hiệ

ện trong qu

n trong quá

átr

trì

ình

sả

ản sinh câu v

n sinh câu và

àkhông xu

không xuấ

ất hi

t hiệ

ện trong c

n trong cá

ác câu đã đư

c câu đã đượ

ợc

văn ph

văn phạ

ạm sinh ra

m sinh ra



l

là

àt

tậ

ập h

p hợ

ợp h

p hữ

ữu h

u hạ

ạn c

n cá

ác ký t

c ký tự

ựk

kế

ết th

t thú

úc, hay ký t

c, hay ký tự

ựcu

cuố

ối

(Terminal Symbols),

(Terminal Symbols), 



N,

N, hay N

hay N 



=

= 



Ngư

Ngườ

ời ta đ

i ta đị

ịnh ngh

nh nghĩ

ĩa b

a bả

ảng ch

ng chữ

ữV = N

V = N 





R

R 

(V

(V++

V

V**) l

) là

àt

tậ

ập h

p hữ

ữu h

u hạ

ạn c

n cá

ác quy t

c quy tắ

ắc (Rules), hay còn g

c (Rules), hay còn gọ

ọi

là

àc

cá

ác s

c sả

ản xu

n xuấ

ất (Productions), ch

t (Productions), chí

ính l

nh là

àc

cá

ác quy t

c quy tắ

ắc vi

c viế

ết l

t lạ

ại v

i vừ

ừa

nó

ói

i ở

ở trên

trên, t

, thư

hườ

ờng c

ng có

ód

dạ

ạng (

ng (

,

, 

), hay

), hay 







S

S 

N l

N là

àký t

ký tự

ự đ

đầ

ầu (Start Symbol)

u (Start Symbol)

25/25/ 7777

Ý ngh

Ý nghĩ

ĩa c

a củ

ủa c

a cá

ác s

c sả

ản xu

n xuấ

ất



M

Mỗ

ỗi s

i sả

ản xu

n xuấ

ất d

t dạ

ạng (

ng (

,

, 

) cho bi

) cho biế

ết :

t :

Ph

Phầ

ần t

n tử

ửbên tr

bên trá

ái (

i (



V

V++) c

) củ

ủa s

a sả

ản xu

n xuấ

ất

đư

đượ

ợc thay th

c thay thế

ếb

bở

ởi ph

i phầ

ần t

n tử

ửbên ph

bên phả

ải (

i (



V

V**)

)



T

Từ

ừS, b

S, bắ

ắt đ

t đầ

ầu qu

u quá

átr

trì

ình s

nh sả

ản sinh câu b

n sinh câu bằ

ằng c

ng cá

ách :

ch :

Á

Áp d

p dụ

ụng s

ng sả

ản xu

n xuấ

ất đ

t đầ

ầu tiên l

u tiên là

àS

S 





Sau đ

Sau đó

ót

tì

ìm trong

m trong 

c

cá

ác ph

c phầ

ần câu

n câu u

u

V

V+ + c

có

óch

chứ

ứa bi

a biế

ến X

n X 

 N

để

ểá

áp d

p dụ

ụng tu

ng tuỳ

ỳý c

ý cá

ác s

c sả

ản xu

n xuấ

ất

t u

u

v

Th

Thự

ực hi

c hiệ

ện m

n mộ

ột c

t cá

ách đ

ch đệ

ệ quy cho đ

quy cho đế

ến khi nh

n khi nhậ

ận đư

n đượ

ợc câu w

c câu w

chỉ

ỉch

chứ

ứa c

a cá

ác ký hi

c ký hiệ

ệu a

u a 



, hay n

, hay nó

ói c

i cá

ách kh

ch khá

ác,

c, w

w 



**



Thông thư

Thông thườ

ờng, n

ng, ngư

gườ

ời ta t

i ta tì

ìm c

m cá

ác ph

c phầ

ần câu

n câu u

u đ

để

ểá

áp d

p dụ

ụng c

ng cá

ác

sả

ản xu

n xuấ

ất l

t lầ

ần lư

n lượ

ợt t

t từ

ừtr

trá

ái qua ph

i qua phả

ải

26/26/ 7777

Mộ

ột s

t số

ố quy ư

quy ướ

ớc



Sau đây l

Sau đây là

àm

mộ

ột s

t số

ố quy ư

quy ướ

ớc khi mô t

c khi mô tả

ả văn ph

văn phạ

ạm G :

m G :

C

Cá

ác bi

c biế

ến A, B, C..., X, Y...

n A, B, C..., X, Y... 

N = V

N = V 





C

Cá

ác ký t

c ký tự

ựthu

thuộ

ộc

c 

 đư

đượ

ợc bi

c biể

ểu di

u diễ

ễn b

n bở

ởi

i a

, b

b, c...

, c...

C

Cá

ác quy t

c quy tắ

ắc, hay s

c, hay sả

ản xu

n xuấ

ất

t 



,

, 

)

) 

 R

, đư

đượ

ợc vi

c viế

ết d

t dạ

ạng :

ng :









hay

hay 



GG



nế

ếu mu

u muố

ốn ch

n chỉ

ỉ đ

đị

ịnh đ

nh đó

ól

là

às

sả

ản xu

n xuấ

ất thu

t thuộ

ộc văn ph

c văn phạ

ạm G

m G

khi l

khi là

àm vi

m việ

ệc c

c cù

ùng l

ng lú

úc v

c vớ

ới nhi

i nhiề

ều văn ph

u văn phạ

ạm kh

m khá

ác nhau

c nhau

Ký t

Ký tự

ự đ

đầ

ầu luôn luôn bi

u luôn luôn biể

ểu di

u diễ

ễn b

n bở

ởi S

i S

C

Cá

ác câu r

c câu rỗ

ỗng đư

ng đượ

ợc bi

c biể

ểu di

u diễ

ễn b

n bở

ởi

i 



27/27/ 7777

Ví

íd

dụ

ụ



Cho văn ph

Cho văn phạ

ạm G = (V,

m G = (V, 

, R, S) v

, R, S) vớ

ới :

i :

N = { S, A, B }

N = { S, A, B }



= {

= { a

, b

b} , S l

} , S là

àký t

ký tự

ự đ

đầ

ầu.

R = { S

R = { S 

A, S

A, S 

B, B

B, B 

bB, B

bB, B 



, A

, A 

aA, A

aA, A 



 }

}

Đ

Để

ểcho g

cho gọ

ọn, khi mô t

n, khi mô tả

ảm

mộ

ột văn ph

t văn phạ

ạm,

m, ngư

ngườ

ời ta thư

i ta thườ

ờng nh

ng nhó

óm

cá

ác quy t

c quy tắ

ắc c

c có

óc

cù

ùng ký t

ng ký tự

ựbên tr

bên trá

ái v

i vớ

ới nhau :

i nhau :

S 

A | B

A | B B

B 

bB |

bB | 

A

A 

aA |

aA | 



Thay v

Thay vì

ìli

liệ

ệt kê h

t kê hế

ết c

t cá

ác th

c thà

ành ph

nh phầ

ần c

n củ

ủa văn ph

a văn phạ

ạm G,

m G,

ngư

ngườ

ời ta ch

i ta chỉ

ỉli

liệ

ệt kê c

t kê cá

ác quy t

c quy tắ

ắc R c

c R củ

ủa văn ph

a văn phạ

ạm m

m mà

àthôi

thôi

Ch

Chẳ

ẳng h

ng hạ

ạn văn ph

n văn phạ

ạm G

m G ở

ởtrên ch

trên chỉ

ỉc

cầ

ần li

n liệ

ệt kê c

t kê cá

ác quy t

c quy tắ

ắc :

c :

G { S

G { S 

A | B ; B

A | B ; B 

bB |

bB | 

;

; A

A 

aA |

aA | 

}

}

Bài tập: Mô tảVP G bằng cách thay thếcác ký hiệu quy ước cho các

đơn vị từvựng trong ví dụ NNLT đơn giản trước đây ?

Bà

ài t

i t ậ

ập

:Mô t

Mô tả

ảVP G b

VP G bằ

ằng c

ng cá

ách thay th

ch thay thế

ếc

cá

ác ký hi

c ký hiệ

ệu quy ư

u quy ướ

ớc cho c

c cho cá

ác

đơn v

đơn vị

ịt

từ

ừv

vự

ựng trong v

ng trong ví

íd

dụ

ụ NNLT đơn gi

NNLT đơn giả

ản trư

n trướ

ớc đây

c đây ?

?28/28/ 7777

Bài tập:

Tìm cách áp dụng lần lượt các sản xuất để sinh ra câu bbbbb ?

Tìm cách biểu diễn các quy tắc tạo tên trong NNLT thành VP và cho ví dụsinh câu

Bà

ài t

i tậ

ập

Tì

ìm c

m cá

ách

ch á

áp d

p d ụ

ụng l

ng lầ

ần lư

n lượ

ợt c

t cá

ác s

c sả

ản xu

n xuấ

ất đ

t để

ểsinh ra câu bbbbb ?

sinh ra câu bbbbb ?

Tì

ìm c

m cá

ách bi

ch biể

ểu di

u diễ

ễn c

n cá

ác quy t

c quy t ắ

ắc t

c tạ

ạo tên trong NNLT th

o tên trong NNLT thà

ành VP v

nh VP và

àcho v

cho ví

íd

dụ

ụsinh câu

sinh câu

Sả

ản sinh câu trong G

n sinh câu trong G



Cho G { S

Cho G { S 

A | B ; B

A | B ; B 

bB |

bB | 

;

; A

A 

aA |

aA | 

}

}



B

Bằ

ằng c

ng cá

ách

ch á

áp d

p dụ

ụng liên ti

ng liên tiế

ếp c

p cá

ác s

c sả

ản xu

n xuấ

ất trong R, ta nh

t trong R, ta nhậ

ận

đư

đượ

ợc c

c cá

ác câu s

c câu sả

ản sinh b

n sinh bở

ởi văn ph

i văn phạ

ạm G

m G



V

Ví

íd

dụ

ụ,

, aaaa

aaaa l

là

àm

mộ

ột câu do G sinh ra b

t câu do G sinh ra bằ

ằng c

ng cá

ách

ch á

áp d

p dụ

ụng l

ng lầ

ần

lư

lượ

ợt c

t cá

ác s

c sả

ản xu

n xuấ

ất :

t :

AÁ

Áp d

p dụ

ụng

ng S

S 

A

aA 

A

A 

aA

aaA

aaA 

A

A 

aA

aaaA

aaaA 

A

A 

aA

aaaaA

aaaaA 

A

A 

aA

aaaa

aaaa 

A

A 





29/29/ 7777

Phé

ép suy d

p suy dẫ

ẫn m

n mộ

ột bư

t bướ

ớc trong G

c trong G



Cho văn ph

Cho văn phạ

ạm G = (N,

m G = (N, 

, R, S),

, R, S),

u

V

V++, v

, v

V

V** đgl c

đgl cá

ác d

c dạ

ạng câu

ng câu



Câu v đư

Câu v đượ

ợc s

c sả

ản sinh t

n sinh t ừ

ừu b

u bằ

ằng

ng m

mộ

ột bư

t bướ

ớc suy d

c suy dẫ

ẫn

n trong G

trong G

(derives

(derives v from u in one step)

v from u in one step) đư

đượ

ợc bi

c biể

ểu di

u diễ

ễn b

n bở

ởi :

i :

u 

GGv

nễ

ễu

u(n

(nế

ếu v

u và

àch

chỉ

ỉn

nế

ếu) :

u) :

u = xu

u = xu’

’y

yu g

u gồ

ồm 3 ph

m 3 phầ

ần x, u

n x, u’

’v

và

ày, x v

y, x và

ày c

y có

óth

thễ

ễr

rỗ

ỗng

v = xv

v = xv’

’y

yv g

v gồ

ồm 3 ph

m 3 phầ

ần x, v

n x, v’

’v

và

ày

u

u’

’

v

v’

’l

là

àm

mộ

ột sx c

t sx củ

ủa G

a G

30/30/ 7777

Phé

ép suy d

p suy dẫ

ẫn nhi

n nhiề

ều bư

u bướ

ớc trong G

c trong G



Cho văn ph

Cho văn phạ

ạm G = (N,

m G = (N, 

, R, S),

, R, S),

u

V

V++, v

, v

V

V** đgl c

đgl cá

ác d

c dạ

ạng câu

ng câu



Câu v đư

Câu v đượ

ợc s

c sả

ản sinh t

n sinh t ừ

ừu b

u bằ

ằng

ng nhi

nhiề

ều bư

u bướ

ớc suy d

c suy dẫ

ẫn

ntrong G

trong G

(derives v from u in several steps)

(derives v from u in several steps) đư

đượ

ợc bi

c biể

ểu di

u diễ

ễn b

n bở

ởi :

i :

u 

**GGv

nễ

ễu



k

k 

0 v

0 và

àv

v00... v

... vkk

V

V++sao cho :

sao cho :

u = v

u = v00

v = v

v = vkk

v

vii

GGv

vi+ 1i+ 1 v

vớ

ới

i 

i, 0

i, 0 

i

i 

k

-1



C

Có

óth

thể

ểvi

viế

ết đ

t đầ

ầy đ

y đủ

ủkhi k nh

khi k nhỏ

ỏ:

u 

**GGv

nễ

ễu

uu =

u = v

v00

GGv

v11

GGv

v22

GG...

... 

GGv

vk k = v

= v

Bài giảng Lý thuyết tính toán: Chương 3 - PGS.TS. Phan Huy Khánh

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi