Tôi có thể rút ngắn cụm từ thông dụng này bằng giao lộ không?

Question

Tôi có điều này L ngôn ngữ mà chỉ chứa một chuỗi: viết ngắn gọn

hơn chuỗi này có 2 (2^n-1) ký tự và tôi muốn giảm bớt nó. Tôi đã nghĩ đến việc sử dụng giao lộ, nếu tôi có thể tìm thấy một số ngôn ngữ thông thường, trong đó giao điểm của cụm từ thông dụng sẽ sinh ra chuỗi này.

tôi có ở đây hàm đệ quy trong trường hợp mà có thể giúp:

function recursiveRegex(charset) { 
if(charset.length == 0) { 
    return []; 
} else { 
    var char = charset.splice(charset.length - 1, 1); 
    var returnVal = recursiveRegex(charset); 
    return returnVal.concat(returnVal) + char ; 
} 
} 

console.log(recursiveRegex(['a1', 'a2', 'a3', 'a4'])); 

Answer 1

này KHÔNG phải là một ngôn ngữ thông thường, vì vậy bạn không thể tìm thấy một ngữ pháp thường xuyên để xác định nó.

Do đó, không có cụm từ thông dụng cho ngôn ngữ này.

A_1: a_1 

A_2: A_1 A_1 a_2 

A_3: A_2 A_2 a_3 

A_n: A_{n-1} A_{n-1} a_n 

Ngữ pháp này xác định ngôn ngữ của bạn và đó không phải là ngữ pháp thông thường.

Bằng chứng trực tiếp rằng ngữ pháp này không xác định ngôn ngữ thông thường là ngữ pháp cần nhiều hơn số vị trí bộ nhớ liên tục để xác định ngôn ngữ. Đối với một số N, một số cần có số phụ thuộc vào N để giữ từ thứ N.

---

Cân nhắc từng biểu tượng bên trái là vị trí bộ nhớ. Nếu bạn muốn làm cho nó thường xuyên, bạn nên có một số hữu hạn các quy tắc. Nếu bạn cần phải làm cho nó hữu hạn, nó nên được thực hiện như vậy:

ATOM: a1

RULE_ {n + 1}: ATOM | RULE_n RULE_n a_ {n + 1}

Để tạo đúng ngôn ngữ này, bạn cần có bộ đếm để biết số a_n để chèn vào từng thời điểm. Nhưng không thể tạo bộ đếm bất kỳ loại nào bằng cách sử dụng các ngữ pháp thông thường.