The Gateway to Computer Science Excellence
0 votes
123 views

Is the following language regular or not?

in Theory of Computation by (103 points)
edited by | 123 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.

by Boss (20.7k points)
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. "
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
50,650 questions
56,192 answers
193,988 comments
94,852 users