∣w∣ is the length of the string.
I know that element in common are something like this...
The left hand side gives the elements in L1 and the right hand side gives the corresponding element in L2
5mod
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