4 Replies - 379 Views - Last Post: 16 August 2018 - 03:56 PM

#1 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 227
  • Joined: 05-January 17

Does the machine accept this language?

Posted 16 August 2018 - 03:25 PM

Hi!

I am learning about whether a language will be accepted by machine. The language I'm studying:
L={w element of {0,1}* : w contains a 1}. Please see attached for the image of the machine!

The answer is that the machine doesn't accept the above language, since potentially could stay at
state q0 non stop and thus never accept a 1.

However, I'm still confused with the above explanation. I would really appreciate if someone could explain clearly why the machine doesn't accept the language.

Thanks :)/>/>

I hope the attachment is showing.

This post has been edited by chloeCodes: 16 August 2018 - 03:45 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Does the machine accept this language?

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12648
  • View blog
  • Posts: 45,822
  • Joined: 27-December 08

Re: Does the machine accept this language?

Posted 16 August 2018 - 03:26 PM

While I don't see an attachment, I would guess that q0 is an accept state. So there exists a string that the machine accepts, which is not in your desired language. Hence, the machine would not accept your language.
Was This Post Helpful? 1
  • +
  • -

#3 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 227
  • Joined: 05-January 17

Re: Does the machine accept this language?

Posted 16 August 2018 - 03:43 PM

Hi Macos,

Thanks for the speedy reply! I have realized this was a problem where I had to differentiate between the notion of a language decider verse language recognizer. In the above machine, it wouldn't reject strings that don't contain a 1, instead it would infinitely loop on the state q0. Thus, the machine would recognize the language, but not decide it :)
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12648
  • View blog
  • Posts: 45,822
  • Joined: 27-December 08

Re: Does the machine accept this language?

Posted 16 August 2018 - 03:48 PM

So you are talking about Turing Machines then, rather than Finite State Automata (this is a pretty important detail that you left out...)? The language in question is regular, and so it is accepted by some DFA (or NFA, if you prefer). If you are working with DFAs/NFAs, they always halt. So a loop on the diagram would not indicate an "infinite loop" (or failure to halt), as in the context of Turing Machines.

In any event, I don't have enough context/information to agree or disagree with your confusion. Your question is certainly context-sensitive. ;)

If you are happy with your answer, then I am glad you have resolved your issue!

This post has been edited by macosxnerd101: 16 August 2018 - 03:49 PM

Was This Post Helpful? 1
  • +
  • -

#5 chloeCodes   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 227
  • Joined: 05-January 17

Re: Does the machine accept this language?

Posted 16 August 2018 - 03:56 PM

Thank you, yes I meant Turing machine, not just any old machine :)/> I'm following complexity and algorithms course on udacity, the question and answer can be found there. The main point is distinguishing between language decider and recognizer. Where a language decider, must have a reject state (not allowed to loop infinitely on a state).

Thanks again for the detailed help!

--> I wish I could upload the image of the machine for others to learn from, for some reason my attached image is not showing :(

This post has been edited by chloeCodes: 16 August 2018 - 03:59 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1