Re: accepting vs. recognizing

From: Hans Hüttel (hans_at_cs.auc.dk)
Date: 07/20/04 

Date: Tue, 20 Jul 2004 15:48:13 +0200

Moritz wrote:

> can anybody please explain if there is a distinction for a Turing-Machine to
> accept or to recognize a recursive language?
> I guess there is none. Hopcroft, Motwani and Ullman talk about
> Turing-Machines accepting words and recognizing languages..

This terminology is sometimes a source of confusion.

A Turing machine accepts a string w if it terminates in an accepting
state, when given w as input.

The language recognized by a Turing machine M is the set

L(M) = { w | M accepts w }

In other words, machines accept strings and recognize languages.

Hans

Relevant Pages