edited by
624 views
2 votes
2 votes

L = {ai bj ck dm} | i+j+k+m is multiple of 13} L is ?

(a) Regular                                                             (b) Context-free
(c) Turing-decidable                                               (d) Turing-Recognizable

edited by

1 Answer

3 votes
3 votes

Answer : A - Regular

$L = \left \{ a^ib^jc^kd^m | i + j+k+m \,\,is\,\,multiple\,\,of\,\,13 \right \}$ is nothing but an Intersection of Two Regular languages.

$L = L_1 \cap L_2 = \left \{ a^*b^*c^*d^* \right \} \bigcap \left \{ w | w \in \left \{ a+b+c+d \right \}^*, Length \,\,of\,\, w \,\,is \,\,divisible\,\, by \,\,13 \right \}$

Both $L_1$ = $\left \{ a^*b^*c^*d^* \right \} $  and $L_2 = $ $ \left \{ w | w \in \left \{ a+b+c+d \right \}^*, Length \,\,of\,\, w \,\,is \,\,divisible\,\, by \,\,13 \right \}$ 

are Regular as First one($L_1$) is a Regular expression itself and the Second one($L_2$) is a Mod 13 language.


NOTE : Since $L$ is Regular, Hence, All the Options are Correct. But the Strongest answer would be Regular.

edited by

Related questions

0 votes
0 votes
0 answers
1
himgta asked Aug 31, 2018
246 views
https://gateoverflow.in/21039/simplified-cfgDoubt in the solution....plz help!
0 votes
0 votes
1 answer
2
himgta asked Aug 7, 2018
356 views
0 votes
0 votes
0 answers
3
himgta asked Jul 31, 2018
399 views
https://gateoverflow.in/188609/me-test-seriesThis question has not been answered, can somebody solve it!
1 votes
1 votes
2 answers
4
himgta asked Jul 31, 2018
2,019 views
Consider the following CFG.S → aSa | bSb | a | b | εFor the above CFG, the total number of strings generated whose length is less than or equal to 8 [exclude the empty...