Sunday 20 September 2015

modular arithmetic - Given $L_1 ={w: |w| bmod 3 >0}$ and $L_2 ={w: |w| bmod 5 =0}$,. What is $L=L_1 cap L_2$ and the grammar it produces?



$\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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...