regular not possible as count needed, cfl too doesnt seem to satisfy the condition

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

L = {a^{i} b^{j} c^{k} d^{m}} | i+j+k+m is multiple of 13} L is ?

(a) Regular (b) Context-free

(c) Turing-decidable (d) Turing-Recognizable

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

+1

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.

And $a^ib^jc^kd^m$ is equivalent to $a^*b^*c^*d^*$ because there is No relation/dependency between them.

0

@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.

0

@deepak poonia cant i say directly that as strings in this langauge form Airthmetic progression and it can be done by FA so its regular..is this reasoning true in this case or not.?

0

@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.

0

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

+1

Its not feasible to design DFA for that question,

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

0

@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!

0

@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?

0

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.

0

@himtga string which are accepted will be first of length 13 than 26 and so on with commmon difference 13..as AP can be done by FA..i have read..dont knw whether it gets applied properly here.?

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,261 answers

182,169 comments

67,679 users