The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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

asked in Theory of Computation by Junior (747 points)
edited by | 101 views
I guess it is C

regular not possible as count needed, cfl too doesnt seem to satisfy the condition
Strongest answer would be Regular.

1 Answer

+2 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.

answered by Boss (16.6k points)
edited ago by
How you came up with the intersection logic?
Because "$i+j+k+m$ is multiple of 13" ... tells us about the Length i.e. Length must be divisible by 13.

And $a^ib^jc^kd^m$ is equivalent to $a^*b^*c^*d^*$ because there is No relation/dependency between them.
Thanks a lot brother!
@deepakk, can you draw a dfa/nfa on this, it would be great for better explanation? :)

@deepakk, can you draw a dfa/nfa on this, it would be great for better explanation? :)

For $L_2$, Mod 13 DFA will have 13 States. So, Drawing that will be hectic and Non-intelligent work. 

Instead, Take it as Mod 2 or 3 DFA and then Draw the DFA for this langauge. Similar idea will be applied for Mod 13. 

Make a DFA $D_1$ for $L_1$ = $a^*b^*c^*d^*$  and DFA $D_2$ for $L_2$ as Mod 2 language. And then Apply Cross Product of States method or Design Prodcut Automata and if required, Minimize.

@deepak poonia cant i say directly that as strings in this langauge form Airthmetic progression and it can be done by FA so its this reasoning true in this case or not.?
@deepakk, i dont think it is a simple mod n language because here it is a*b*c* and not (a+b+c)* , ordering has to be followed. Please check.

 i dont think it is a simple mod n language because here it is a*b*c* and not (a+b+c)* , ordering has to be followed. 

Answer made more clear. Check again.

$L_2$ is simple Mod 13 language. So, Construct a separate DFA $D_2$ for that.

Construct DFA $D_1$ for $L_1$.

Now, Apply Cross product method for $D_1$ and $D_2$ and you will have the DFA for the language $L$.


Its not feasible to design DFA for that question,

I took small example of this kind ,{anbm | n+m is divisible by 3}.



@prashant can you check my above doubt in comments..can we say such thing here..?
@Prashant sir this one is wrong as it is not accepting aabbbb
@prashant, it is also accepting aaabaaab

@Deepakk Poonia (Dee) @Prashant, Sir I always get confused in the questions of type whether a language is regular of CFL, How to solve such type of questions,Please provide a simple way!

@Shubham shukla 6, How are u saying that the strings in the given language are in A.P as I am not able to get it?
now check i hope this time is correct !!
himgta by design dfa . Take same type of question with less value like i took 3 instead of 13. By doing this you get logic either you can design for 13 or not.
@himtga string which are accepted will be first of length 13 than 26 and so on with commmon difference AP can be done by FA..i have read..dont knw whether it gets applied properly here.?


you are partially correct , here kind of string generated also matter, like if question is a2n+1 then your logic is correct without design any dfa. Try to generate few strings you will get idea about language .

@deepakk, @prashant i have got it. Thanks

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,995 questions
44,571 answers
43,637 users