Các Sự khác biệt chính giữa biểu thức chính quy và ngữ pháp không có ngữ cảnh là biểu thức chính quy giúp mô tả tất cả các chuỗi của một ngôn ngữ thông thường trong khi ngữ pháp không có ngữ cảnh giúp xác định tất cả các chuỗi có thể có của một ngôn ngữ không có ngữ cảnh.

Ngữ pháp biểu thị các quy tắc cú pháp cho cuộc trò chuyện bằng ngôn ngữ tự nhiên. Khoa học Máy tính sử dụng lý thuyết về ngôn ngữ chính thức ở một mức độ lớn. Vào năm 1956, Noam Chomsky đã đưa ra một mô hình toán học về ngữ pháp để viết ngôn ngữ máy tính. Khi có thể lấy một tập hợp tất cả các chuỗi từ một ngữ pháp, người ta nói rằng ngôn ngữ được tạo ra từ ngữ pháp đó. Hai loại ngữ pháp là ngữ pháp thông thường và ngữ pháp không theo ngữ cảnh. Bất kỳ ngôn ngữ nào có thể được mô tả bằng biểu thức chính quy đều là ngôn ngữ chính quy. Ngữ pháp tự do theo ngữ cảnh là sự tổng quát hóa của biểu thức chính quy. Có thể sử dụng cụm từ thông dụng để viết ngôn ngữ thông thường và ngữ pháp không có ngữ cảnh để viết ngữ pháp không có ngữ cảnh.

Biểu thức chính quy, Ngữ pháp không theo ngữ cảnh

Biểu thức chính quy là gì

Ngữ pháp thông thường tạo ra các ngôn ngữ thông thường. Ngữ pháp này có một đầu cuối duy nhất ở phía bên trái và một phía bên phải bao gồm một đầu cuối hoặc một đầu cuối duy nhất theo sau là một không đầu cuối duy nhất. Nó có thể có một quy tắc sản xuất như sau.

X -> a hoặc X -> a Y

Trong đó X, Y ϵ N (không phải đầu cuối) và a ϵ T (đầu cuối)

Biểu thức chính quy giúp viết ngữ pháp thông thường để mô tả các ngôn ngữ thông thường.

Một biểu thức chính quy đại diện cho một tập hợp các chuỗi nhất định theo kiểu đại số. Một số quy tắc quan trọng cần tuân theo khi viết một biểu thức chính quy như sau.

1. Các ký hiệu đầu cuối, ký hiệu null và biểu tượng trống là các biểu thức chính quy.
2. Sự kết hợp của hai biểu thức chính quy là một biểu thức chính quy.
3. Nối hai biểu thức chính quy là một biểu thức chính quy.
4. Lặp lại hoặc đóng là một biểu thức chính quy.

Biểu thức chính quy cho tập hợp {0, 1, 2} như sau.

R = 0 + 1 + 2

Tập hợp {abb, a, b, bba} có thể được biểu diễn bằng biểu thức chính quy sau.

R = abb + a + b + bba

Hãy xem xét tập hợp, {ϵ, 0, 00, 000,…}

Ε là chuỗi rỗng. Biểu thức chính quy là R = 0 *. Điều này thể hiện sự đóng của biểu tượng bao gồm cả biểu tượng trống.

Trong tập hợp {1, 11, 111, 1111,…..}

Biểu thức chính quy là R = 1 ^+. Dấu + này biểu thị sự đóng của một biểu tượng không bao gồm biểu tượng trống.

Ngữ pháp miễn phí theo ngữ cảnh là gì

Trong lý thuyết ngôn ngữ chính thức, Ngôn ngữ không theo ngữ cảnh (CFL) là một ngôn ngữ được tạo ra bởi Ngữ pháp không theo ngữ cảnh. Bốn tham số xác định ngữ pháp tự do ngữ cảnh (G).

G = {V, ∑, S, P}

V: Tập hợp các ký hiệu biến hoặc không đầu cuối.

∑: Tập hợp các ký hiệu đầu cuối

S: Biểu tượng Bắt đầu

P: Quy tắc sản xuất

Ngữ pháp miễn phí theo ngữ cảnh có định dạng sau cho quy tắc sản xuất.

A -> a trong đó a = {V, ∑} * và A ϵ V

Một ví dụ về Ngữ pháp miễn phí theo ngữ cảnh như sau. Mỗi sản xuất bao gồm một ký hiệu không phải đầu cuối và một biểu thức chính quy.

Để tạo một ngôn ngữ tạo ra một số lượng bằng nhau của a và b ở định dạng của NS . Ngữ pháp tự do theo ngữ cảnh như sau.

G = {(S, A), (a, b), (S -> aAb, A -> aAb | ϵ)}

Xem xét biểu tượng bắt đầu,

S -> a A b

Bằng cách áp dụng A -> aAb

→ a a A b b

Bằng cách áp dụng lại A -> aAb,

→ a a a A b b b

Bằng cách áp dụng A -> ϵ (Biểu tượng này biểu thị một chuỗi trống)

→ a a a b b b

→ a ³ NS ³

Khi xem xét đầu ra, số a bằng số b. Nó có một NS mẫu đơn.

Mối quan hệ giữa biểu thức chính quy và ngữ pháp tự do theo ngữ cảnh

Sự khác biệt giữa biểu thức thông thường và ngữ pháp tự do theo ngữ cảnh

Sự định nghĩa

Biểu thức chính quy là một khái niệm trong lý thuyết ngôn ngữ hình thức, là một chuỗi các ký tự xác định một mẫu tìm kiếm. Ngữ pháp tự do theo ngữ cảnh là một loại ngữ pháp chính thức trong lý thuyết ngôn ngữ chính thức, là một tập hợp các quy tắc sản xuất mô tả tất cả các chuỗi có thể có trong một ngôn ngữ chính thức nhất định.

Sử dụng

Biểu thức chính quy giúp biểu diễn các tập hợp chuỗi nhất định theo kiểu đại số. Nó giúp đại diện cho các ngôn ngữ thông thường. Ngữ pháp không có ngữ cảnh giúp xác định tất cả các chuỗi có thể có của một ngôn ngữ không có ngữ cảnh.

Phần kết luận

Biểu thức chính quy là một phương thức để đối sánh mẫu. Đây là một phương pháp linh hoạt cung cấp một phương tiện linh hoạt và ngắn gọn để khớp các chuỗi văn bản. Nó định nghĩa tất cả các chuỗi bằng ngôn ngữ thông thường. Mặt khác, ngữ pháp không có ngữ cảnh cho phép xác định tất cả các chuỗi thuộc về một ngôn ngữ không có ngữ cảnh. Sự khác biệt giữa biểu thức chính quy và ngữ pháp không có ngữ cảnh là các biểu thức chính quy giúp mô tả tất cả các chuỗi của một ngôn ngữ thông thường trong khi ngữ pháp không có ngữ cảnh giúp xác định tất cả các chuỗi có thể có của một ngôn ngữ không có ngữ cảnh.

Thẩm quyền giải quyết:

1. "Biểu thức chính quy." Www.tutorialspoint.com, Tutorials Point, ngày 8 tháng 1 năm 2018, có sẵn tại đây.2. “Giới thiệu ngữ pháp không theo ngữ cảnh”. Www.tutorialspoint.com, Tutorials Point, ngày 8 tháng 1 năm 2018, Có sẵn tại đây.

Hình ảnh lịch sự:

1. “Toolbaricon RegEx” của M0tty - Tác phẩm riêng (CC BY-SA 4.0) qua Commons Wikimedia