search
Log In
0 votes
188 views

Is the following language regular or not?

in Theory of Computation
edited by
188 views
1
yes. (modular counting is regular )
0
Can u please elaborate how is it possible to construct a dfa/nfa  for this problem.

:)
0
state/inputs x y z
A(final state) B B B
B C C C
C D D D
D E E E
E A A A

 

0
What are the other options bro ??

It is general fact that modular counting is always regular
0
Other options is to make a DFA or NFA for it or use pumping lemma to show that its not regular.

A language is said to be regular if you can draw a Finite Automata for it.

Every mod n counting has n states and the remainder that we want is the final state.

for example mod 3 counting will have 3 states and if we want remainder as 1 then the middle state will be the final state.

1 Answer

0 votes
state/inputs x y z
A B B B
B C C C
C D D D
D E E E
E A A A

A is the initial as well as final state.

since we can draw a finite automata for this language

=> the language is regular.

0
Thanks for the solution.

I still have a doubt that while providing the loop back to state A from state E there will be strings out of the language and they also get accepted right?. Also x should be followed by y and then by z. Please clear this one.  

Appreciate that :)
0
yes.... you are correct. xzy will also be accepted. Here i only checked l+m+n mod 5 and forgot to check the order. :(
0
Yeah. The one's who came up with this question are saying it as a regular language. Still now am confused of their statement . Is there a way to realize this?.

" Whenever we provide a feedback transition from a state then the language acts like kleen closure. "

Related questions

0 votes
0 answers
3
294 views
Consider the following language over ∑={0,1} $L_{1} = \left \{ a^{\left \lfloor \frac{m}{n} \right \rfloor}| m,n \geq 1; n<m \right \}$ $L_{2} = \left \{ a^{m^{n}}| m,n \geq 1; n<m \right \}$ Which of them are regular? Both L1 and L2 Only L2 Only L1 None Ans. A. Both Please explain.
asked Jan 15, 2019 in Theory of Computation MiNiPanda 294 views
...