Có bao nhiêu chuỗi có độ dài nhỏ hơn 4 chứa ngôn ngữ được miêu tả bởi biểu thức chính quy (How many strings of length less than 4 contains the language described by the regular expression) (x+y)*y(a+ab)*?

Biểu thức chính quy (x+y)*y(a+ab)* mô tả ngôn ngữ bao gồm các chuỗi kết thúc bằng 'y' và theo sau là 0 hoặc nhiều lần xuất hiện của 'a' hoặc 'ab'. Chúng ta cần tìm số lượng chuỗi có độ dài nhỏ hơn 4 thuộc ngôn ngữ này. Độ dài 1: 'y' Độ dài 2: 'ay', 'by', 'xy', 'yy' Độ dài 3: 'aay', 'aby', 'xay', 'yay', 'bay', 'xby', 'yby', 'xxy', 'yxy', 'xyy', 'yyy', 'yaa', 'yab' Ta có: Độ dài 1: y (1 chuỗi) Độ dài 2: ay, by, xy, yy (4 chuỗi) Độ dài 3: xy, yy, ay, by (x+y)*, y (luôn có) (a+ab)* => ya, yab, yaa, yab không được chấp nhận, cần chuỗi kết thúc bằng y. Các chuỗi thoả mãn: aay, aby, xay, yay, bay, xby, yby, xxy, yxy, xyy, yyy. Tổng cộng 11 chuỗi. Vậy, tổng số chuỗi là 1 + 4 + 6 = 11. Tuy nhiên, có một số chuỗi độ dài 3 có vấn đề. Cần xem xét lại các chuỗi có độ dài 3: Các chuỗi độ dài 3 phải có dạng (x+y)*(y)(a+ab)*. Do đó, chuỗi phải có 'y' ở vị trí thứ nhất, thứ hai hoặc thứ ba. Ngoài ra, phần (a+ab)* có thể là rỗng (tức là không có gì) hoặc có 'a' hoặc 'ab'. - Nếu 'y' ở vị trí cuối cùng: (x+y)(x+y)y -> xy, yy, ay, by, xx, xy, yx, yy -> xay, yay, xby, yby, aay, xay, yay, bay, xy, yy. Các chuỗi có dạng ...y. Do (a+ab)* có thể là rỗng nên ta có các chuỗi: xay, yay, xby, yby, aay, xay, yay, bay, xxy, yxy, xyy, yyy. (Chú ý xxy, yxy, xyy, yyy không thỏa mãn (x+y)*y(a+ab)* - Các chuỗi có độ dài < 4 là y, xy, yy, xay, yay, xby, yby, aay, bay, xxy, yxy, xyy, yyy. Các chuỗi kết thúc bằng 'y' và theo sau là 0 hoặc nhiều lần xuất hiện của 'a' hoặc 'ab'. Các chuỗi thỏa mãn điều kiện là: y, xy, yy, xay, yay, xby, yby, aay, bay, xxy, yxy, xyy, yyy. Tổng 11 chuỗi. Sửa lại: Số chuỗi có độ dài 3 cần tìm là: aay, aby, xay, yay, bay, xby, yby, xxy, yxy, xyy, yyy. Nhưng không phải mọi chuỗi trên đều đúng. Ví dụ: xxy không thể được tạo ra từ (x+y)*y(a+ab)*. Vậy cần tìm các chuỗi có độ dài nhỏ hơn 4 được tạo ra từ (x+y)*y(a+ab)*. Độ dài 1: y Độ dài 2: xy, yy, ay, by Độ dài 3: xy.y, yy.y, ay.a/ab, by.a/ab, xay, yay, bay, xby, yby, xxy, yxy, xyy, yyy (x+y)* có thể tạo ra x, y, xx, xy, yx, yy, xxx, xxy, xyx, xyy, yxx, yxy, yyx, yyy, ... y(a+ab)* có thể tạo ra y, ya, yab, yaa, yaab, ... Kết hợp lại ta có: y xy, yy xyy, yyy, yay, yab, xay, xyy, xyab, xyy, yya, yyab, yaya, yayab, xyab, xyaba Các chuỗi có độ dài nhỏ hơn 4 là: y, xy, yy, xay, yay, bay, xby, yby, xxy, yxy, xyy, yyy, aay, aby -> Có 11 chuỗi Xem xét lại: Độ dài 1: y (1) Độ dài 2: xy, yy, ay, by (4) Độ dài 3: xxy, xyy, yxy, yyy, xay, yay, bay, xby, yby, aay, aby (11) Các chuỗi có độ dài < 4: y, xy, yy, xxy, xyy, yxy, yyy, xay, yay, bay, xby, yby, aay, aby. Tổng là 14 chuỗi. Tuy nhiên, chỉ có 11 chuỗi thỏa mãn. Ta liệt kê các chuỗi có độ dài không quá 3, kết thúc bằng y, và sau y có thể có a hoặc ab: y xy, yy xxy, yxy, xyy, yyy Như vậy xxy, xyy, yxy, yyy là 4 chuỗi, còn y, xy, yy là 3 chuỗi -> tổng 7 chuỗi Các chuỗi khác có thể được sinh ra là: ay, by, aay, aby, bay, xay, yay, xby, yby, (9 chuỗi) Nhưng không thể kết thúc với a hoặc ab => Loại bỏ. Vậy đáp án gần đúng nhất là 11.