Czy mogę skrócić to wyrażenie regularne za pomocą przecięcia?

Question

Mam ten język L, który zawiera tylko jeden wpis: pisemnej bardziej zwięźle

Ten ciąg ma 2 (2^n-1) znaki i chcę, aby go zmniejszyć. Myślałem o użyciu przecięcia, jeśli mogę znaleźć kilka języków regularnych, w których przecięcie ich wyrażeń regularnych spowoduje ten ciąg.

Mam tu rekurencyjnej funkcji w przypadku, która pomogłaby:

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

To nie jest zwykłym językiem, więc nie można znaleźć regularną gramatykę, aby go zdefiniować.

W związku z tym nie ma wyrażenia regularnego dla tego języka.

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 

Ta gramatyka określa twój język i nie jest to zwykła gramatyka.

Bezpośrednim dowodem na to, że gramatyka nie definiuje zwykłego języka, jest to, że do zdefiniowania języka potrzeba więcej niż stałej liczby miejsc pamięci. Dla danego N, potrzebna jest liczba w zależności od N, aby zachować jedno słowo w słowie N.

---

Rozważ każdy lewy symbol lokalizacji pamięci. Jeśli chcesz zrobić to regularnie, powinieneś mieć skończoną liczbę reguł. Jeśli musisz zrobić to skończona, należy to zrobić tak:

ATOM: a1

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

Aby poprawnie utworzyć ten język, potrzebny jest licznik, aby wiedzieć, co należy wstawić w danym momencie: a_n. Nie można jednak tworzyć liczników za pomocą zwykłych gramatyk.