# Does the machine accept this language?

Page 1 of 1

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

### #1 chloeCodes

Reputation: 4
• 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

• Games, Graphs, and Auctions

Reputation: 12648
• 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.

### #3 chloeCodes

Reputation: 4
• 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

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12648
• 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.

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

### #5 chloeCodes

Reputation: 4
• 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