wanted: simple TM for non-CF language

Article View: comp.theory

Article #1768

#1768

From: Koen Versmissen
Date: Thu, 30 May 1991 11:39

10 lines
829 bytes

I'm looking for a Turing machine of the standard kind (i.e. just one tape; a tape which is infinite on both sides is OK) which recognizes a non context-free
language. The simpler this TM is (i.e. the smaller the number of states), the
better. 
Thanks!  Koen.

-- 
Koen Versmissen, Rijksuniversiteit Utrecht, Nederland.
(jagversm@praxis.cs.ruu.nl).

The pain of war can not exceed, the woe of aftermath - Led Zeppelin

Technical Details

Message-ID: <1991May30.113935.17974@cs.ruu.nl>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!alchemy!jagversm

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!alchemy!jagversm
From: jagversm@cs.ruu.nl (Koen Versmissen)
Newsgroups: comp.theory
Subject: wanted: simple TM for non-CF language
Keywords: Turing machines, non-CFL
Message-ID: <1991May30.113935.17974@cs.ruu.nl>
Date: 30 May 91 11:39:35 GMT
Organization: Utrecht University, Dept. of Computer Science
Lines: 10