Ngữ cảnh miễn phí ngữ cảnh cho không phải palindrome

Question

Tôi cần một CFG sẽ tạo ra các chuỗi khác với palindromes. Giải pháp đã được cung cấp và như sau (Giới thiệu về lý thuyết tính toán - Sipser)

R -> XRX | S 
S -> aTb | bTa 
T -> XTX | X | <epsilon> 
X -> a | b 

Tôi có ý tưởng chung về cách thức hoạt động của ngữ pháp này. Nó yêu cầu chèn một chuỗi con có các bảng chữ cái không bằng nhau tương ứng trên một nửa của nó, thông qua việc sản xuất S -> aTb | bTa, do đó đảm bảo rằng một palindrome không bao giờ có thể được tạo ra.

Tôi sẽ viết ra ngữ nghĩa của hai tác phẩm đầu tiên như tôi đã hiểu nó,

• S tạo ra chuỗi mà không thể palindromes vì ​​1 và bảng chữ cái cuối cùng không bằng nhau
• R bao gồm ít - S là một chuỗi phụ đảm bảo rằng nó không bao giờ là palindrome.

Tôi không hiểu hoàn toàn ngữ nghĩa của quá trình sản xuất thứ ba, tức là.

T -> XTX | X | <epsilon> 
    X -> a | b 

Cách tôi xem, T có thể tạo bất kỳ kết hợp nào của a và b, tức là {a, b} *. Tại sao nó không giống như

T -> XT | <epsilon> 
X -> a | b 

Không phải là hai tương đương? Vì sau này trực quan hơn, tại sao nó không được sử dụng?

Answer 1

Việc xây dựng cuốn sách Tôi tin là cho thấy một số đối xứng cho việc đọc tốt hơn.

Nó có nghĩa là nó đầu tiên xây dựng bất cứ điều gì, T. Sau đó, có một wrapper S, do đó nó sẽ không còn là một palindrome S, và sau đó xây dựng tất cả mọi thứ trên nó.

Loại thứ hai có vẻ trực quan. Tuy nhiên, nếu bạn nghĩ về định nghĩa hoặc xây dựng palindrome, bạn có thể hiểu lý do tại sao viết theo cách đó có ý nghĩa.

Nếu bạn có một palindrome, bạn sẽ xây dựng một cái gì đó như thế này

T -> ATA | bTb | a | b | epsilon

Và nếu chúng ta muốn vi phạm xây dựng, chúng tôi chỉ cần phải chắc chắn rằng có một lớp trông như thế này (tôi sử dụng T là một lớp và S để một cái gì đó một bước sau khi T)

S -> ATB

Và lớp khác mà chúng tôi thường không quan tâm

S -> ATA | aTb | bTa | bTb

Do đó tạo thành lớp bên trong (T) và lớp ngoài (R) và lớp vi phạm cấu trúc palindrome (S). Mặc dù T nghĩ là có vẻ dư thừa, nhưng nó tạo thành một công trình tương tự như R, do đó thể hiện ý định xây dựng.

Answer 2

Định nghĩa của T trong ngữ pháp đó thực sự dường như là biến chứng không cần thiết. T có thể tạo bất kỳ chuỗi nào là a s và b giây, vì vậy định nghĩa đơn giản hơn sẽ tốt hơn.

Tôi chỉ có thể đoán rằng các sản phẩm được đưa ra vì chúng là do tính chất của nhà máy xúc xích khi viết sách.

ORIGINAL WRONG ĐÁP:

Họ không phải là tương đương, vì X bản thân không thể <epsilon>, và T không phải là bất kỳ sự kết hợp của a và b. T chỉ có thể mở rộng thành palindrome (bao gồm palindrome trống, một ký tự đơn hoặc palindrome có ký tự trung tâm chưa được ghép nối).

Nếu X có thể trống, thì T có thể mở rộng thành bất kỳ thứ gì, nhưng không thể.

LƯU Ý

Câu trả lời này được dựa trên giả thiết rằng ý định của tác giả đối với việc sản xuất T -> XTX là hai giống hệt nhau không bến trong thay phải đại diện cho chuỗi giống hệt nhau của nhân vật. Vì tôi không có văn bản để xem xét, tôi không biết nếu giả định này được thành lập tốt, ngoại trừ việc nó được thúc đẩy bởi chính câu hỏi đó. Giả thuyết này có thể là một sai lầm của tác giả nếu đó không phải là trường hợp ở nơi khác. Tôi nghĩ rằng, nói chung, yêu cầu này không đúng với các ngữ pháp không có ngữ cảnh.

Các sản phẩm đúng sẽ là:

R -> aRa | bRb | S 
S -> aTb | bTa 
T -> aTa | bTb | a | b | <epsilon> 

Answer 3

tôi thấy định nghĩa này của một tổ chức phi palindrome khá trực quan. Tôi cho rằng tác giả bắt đầu với một định nghĩa cho một palindrome

R -> aRa | bRb | a | b | <epsilon> 

và bây giờ hỏi, làm thế nào định nghĩa này có thể được "hủy hoại".

Tức là, anh mở ra định nghĩa ba lần, đã trao đổi một aRa | bRb bởi aRb | bRa và tổng quát các sản phẩm còn lại thành (a|b)R(a|b).

Answer 4

Cách tốt nhất để đảm bảo rằng bạn có một ngữ pháp mà tạo ra chỉ phi palindromes như sau: Xác định:

• Pal - Ngôn ngữ của palindromes
• {a, b} * - Các ngôn ngữ chứa tất cả các chuỗi trên bảng chữ cái {a, b}
• Non-Pal - Ngôn ngữ của tất cả các chuỗi không phải là palindromes (tức là không Pal)

Observer rằng phi Pal = {a, b} * - Pal

Ngữ pháp cho Pal được biết là như sau:

• S -> lambda | a | b | aSa | BSB

Ngữ pháp cho {a, b} * có thể được viết như sau:

• S -> lambda | Sa | Sb

Bây giờ để xây dựng các văn phạm phi Pal các vấn đề sau:

• Nếu x là một phần tử của phi Pal thì:
  • AXA là một phần tử của phi Pal
  • BXB là một phần tử của phi Pal
• Nếu y là một phần tử của {a, b} * sau đó:
  • ayb là một phần tử của phi Pal
  • bya là một phần tử của phi Pal

Kết hợp tất cả các thông tin này ngữ pháp cho người không Pal sẽ là:

• S -> aSa | bSb | aAb | bAa
• A -> lambda | Aa | Ab

Tôi hy vọng điều này làm rõ điều

Answer 5

Bất kỳ Không Palindrome có thể được phân chia theo trung bình, như rằng x (k)! = X (k + n)

n = nửa chiều dài x (i) = ký tự thứ i vị trí

giữ ý nghĩ đó là một giải pháp đơn giản sẽ là

R -> aRa | bRb | T 
T -> aSb | bSa 
S -> aRa | bRb | a | b | T | episoln 

Nó có thể tạo ra tất cả palindromes phi