0
$\begingroup$

If we say that the grammar for the language $L = \{ww \mid w \in \{a,b\}^*\}$, is:

$\begin{align} S &\rightarrow A_1A_2S \mid B_1B_2S \mid Z_2\\ A_2A_1 &\rightarrow A_1A_2\\ A_2B_1 &\rightarrow B_1A_2\\ B_2A_1 &\rightarrow A_1B_2\\ B_2B_1 &\rightarrow B_1B_2\\ A_2Z_2 &\rightarrow Z_2a\\ B_2Z_2 &\rightarrow Z_2b\\ Z_2 &\rightarrow Z_1\\ A_1Z_1 &\rightarrow Z_1a\\ B_1Z_1 &\rightarrow Z_1b\\ Z_1 &\rightarrow \lambda\\ \end{align}$

Here, the characters for each word are generated in the order they appear in a word $x \in L$ in pairs $A_1A_2$ and $B_1B_2$, sorted using rules like $A_2B_1 \rightarrow B_1A_2$ and then converted with the end character, $Z_2$.

It can be seen that we could easily adapt this grammar to recognise the language $L = \{www \mid w \in \{a,b\}^*\}$, by changing the start rule to $S \rightarrow A_1A_2A_3S \mid B_1B_2B_3S \mid Z_3$ and then adding more sorting and converting rules accordingly.

I am struggling to see how we can generalise this to the language $L = \{w^i \mid w \in \{a,b\}^*,i \ge 2\}$, however.

Can you use a rule that looks like $S \rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i$, where $i \ge 2$?

If so, can we use sorting rules that look like:

$A_kB_j \rightarrow B_jA_k$, where $1 \le j < k \le i$,

are you allowed to use variables in grammars like that? If so, you could just write the whole grammar as:

$\begin{align} S &\rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i,\text{ where } i \ge 2.\\ A_kA_j &\rightarrow A_jA_k;\\ A_kB_j &\rightarrow B_jA_k;\\ B_kA_j &\rightarrow A_jB_k;\\ B_kB_j &\rightarrow B_jB_k,\text{ where } 1 \le j < k \le i.\\ A_kZ_k &\rightarrow Z_ka;\\ B_kZ_k &\rightarrow Z_kb;\\ Z_k &\rightarrow Z_{k-1},\text{ where } 1 \le k \le i.\\ Z_0 &\rightarrow \lambda\\ \end{align}$

I have never seen a grammar with variables like this though. But I guess they aren't really variables, because $i$ needs to be specified before the computation begins. So, what you would actually be doing is choosing some $i$ and then instantiating a version of that grammar, specifially for a given $i$. Once the computation has begun, there are no actual variables in the grammar and, effectively, we are just providing rules to build a grammar for the language, based on some $i$.

I can think of an algorithm for a Turing machine that could recognise that language (by partitioning the input string $w$ in all possible ways such that $|w|\text{ mod }n = 0$, where $n$ is the number of substrings, and then checking each partition to see if any of them have exactly the same substrings), so the language must be recursively enumerable - I just can't think how to write something like this as a grammar without making rules with variables (if you arent allowed to.. if you are allowed to then I think what I have is okay..)

EDIT:

I think I might have come up with a way of solving the problem without using index variables:

$\begin{align} S &\rightarrow LZ_1XR\\ X &\rightarrow A_0X \mid B_0X \mid \lambda\\ Z_1A_0 &\rightarrow A_1A_0Z_1\\ Z_1B_0 &\rightarrow B_1B_0Z_1\\ A_0A_1 &\rightarrow A_1A_0\\ A_0B_1 &\rightarrow B_1A_0\\ B_0A_1 &\rightarrow A_1B_0\\ B_0B_1 &\rightarrow B_1B_0\\ LA_1 &\rightarrow A_1L\\ LB_1 &\rightarrow B_1L\\ Z_1R &\rightarrow RZ_0 \mid Y_0\\ A_0Z_0 &\rightarrow Z_0A_0\\ B_0Z_0 &\rightarrow Z_0B_0\\ LZ_0 &\rightarrow LZ_1\\ A_0Y_0 &\rightarrow Y_0a\\ B_0Y_0 &\rightarrow Y_0b\\ LY_0 &\rightarrow Y_1\\ A_1Y_1 &\rightarrow Y_1a\\ B_1Y_1 &\rightarrow Y_1b\\ Y_1 &\rightarrow \lambda\\ \end{align}$

Here, an initial string $w$ is generated between $L$ and $R$ markers using $A_0$ and $B_0$ non-terminals, then the $Z_1$ character is moved to the right of the string, making a copy of the word in $A_1$ and $B_1$ non-terminals which are then shuffled to the left of the $L$ marker, and this process is repeated until you have $i$ copies of the string $w$, at which point the $Z_1$ changes and runs across the string to the left changing all the non-terminals into terminals.

I think this should work fine.. but it is a pretty complicated grammar, so my initial question still remains, are you allowed to use index variables to make rules to generate grammars like I did in the original question?

$\endgroup$
3
$\begingroup$

Can you use a rule that looks like $S \rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i$, where $i \ge 2$?

No. Grammar rules consist of explicitly given finite strings of terminals and non-terminals on each side of the arrow, and a grammar may contain only finitely many rules. The first restriction rules out the "for all $i\ge 2$" part of your rule, and the second part rules out viewing that single rule as standing for the infinite sequence of rules $A_1\to B_1$, $A_1A_2\to B_1B_2$, $\dotsc$.

Note that, if rules are allowed to be infinite (in size or number) then you can write a grammar for every language, as you can just give the infinite rule $A\to s_1\mid s_2\mid \dots$.

$\endgroup$
  • $\begingroup$ Ah yes, of course. I should have thought about the fact that you could just write a grammar for any language if you allow an unbounded number of rules. Thanks for that. I like my alternative solution anyway :) $\endgroup$ – guskenny83 Oct 7 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.