$\mid w \mid$ is the length of the string.
I know that element in common are something like this...
The left hand side gives the elements in $L_1$ and the right hand side gives the corresponding element in $L_2$
$ 5 \bmod 3 \Rightarrow 5 \bmod 5$
$ 10 \bmod 3 \Rightarrow 10 \bmod 5$
$ 20 \bmod 3 \Rightarrow 20 \bmod 5$
$ 25 \bmod 3 \Rightarrow 25 \bmod 5$
$ 35 \bmod 3 \Rightarrow 35 \bmod 5$
$ 40 \bmod 3 \Rightarrow 40 \bmod 5$
$ 45 \bmod 3 \Rightarrow 45 \bmod 5$
$ 55 \bmod 3 \Rightarrow 55 \bmod 5$
and so on...
So the set of lengths $\{5,10,20,25,35,40,45,55...\}$ are all in $L=L_1 \cap L_2$
The length of each string starting with 5 alternates in size between $5,10,5,10,5,10...$
If let's say the alphabet is $\sum = \{a\}$
How does one conjecture $L$ and the grammar that produces it? I'm stuck been at it for a while, any help would be appreciated.
Answer
The first part of your question boils down to a standard exercise in arithmetic.
You can use the Chinese remainder theorem to show that the conjunction of the conditions $|w| \bmod 3 > 0$ and $|w| \bmod 5 = 0$ is equivalent to
$${|w| \bmod {15} = 5} \quad \text{or}\quad |w| \bmod {15} = 10 $$
If $A$ is the alphabet, the corresponding language is $(A^{15})^*(A^5 + A^{10})$.
Writing a grammar for this language should now be an easy, also somewhat tedious, exercise.
No comments:
Post a Comment