GATE CSE
First time here? Checkout the FAQ!
x
0 votes
22 views
The numbers 1,2,4,8,…2n,…1,2,4,8,…2n,… written in unary

Is regular or not??

if not please justify??
asked in Theory of Computation by Active (2.4k points)   | 22 views

1 Answer

+2 votes
Best answer
It is not a regular language.

The reason is there is NO DFA that could accept this language.

If the language is infinite, there must be a pattern in it for being a regular language.The pattern means that..length of strings should be in AP that could be checked through loops.

In this language, no loop is possible.

I hope this helps.
answered by Junior (699 points)  
selected by
@vivek jain Actually i was thinking for below dfa but i got your point below dfa accept all strings given in language {1,11,1111,11111111,.......}no [email protected] but it also accepts unwanted strings{111,11111....} so not accepted right!
yeah..the DFA must also reject the strings not in the language.

Related questions



Top Users Aug 2017
  1. Bikram

    5266 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3514 Points

  4. manu00x

    3492 Points

  5. rahul sharma 5

    3188 Points

  6. makhdoom ghaya

    2700 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2090 Points

  10. pawan kumarln

    1876 Points


25,071 questions
32,225 answers
75,102 comments
30,232 users