From steescoth@yahoo.com Sat Oct 29 02:09:53 2005 Date: Sat, 29 Oct 2005 05:14:25 -0000 From: steescoth Reply-To: comp-sci-theory@yahoogroups.com To: comp-sci-theory@yahoogroups.com Subject: [comp-sci-theory] Turing machine that recognizes a specific language [ The following text is in the "iso-8859-1" character set. ] [ Your display is set for the "US-ASCII" character set. ] [ Some characters may be displayed incorrectly. ] Below I have constructed a Turing machine that recognizes the set L={0^n 1 ^n 0^n, n>=1}. Is my construction correct? I tried all types of inputs and they worked so it should be correct. This should be easy to look over but I have a feeling only Mike Christoff will respond. ________________________________________________________ input alphabet: {0,1} tape alphabet: {0,1,X,S,B} states: Q={q_0, q_1, q_2, q_3, q_4, q_r, q_a} transition function: __________________________________________ q_0 1 | q_r B | q_r 0 | q_1 S R ___________________________________________ q_1 0 | q_1 0 R 1 | q_2 X R X | q_1 X R B | q_r ___________________________________________ q_2 0 | q_3 X L 1 | q_2 1 R X | q_2 X R B | q_r ___________________________________________ q_3 0 | q_1 S R 1 | q_3 1 L X | q_3 X L S | q_4 S R ___________________________________________ q_4 0 | q_r 1 | q_r X | q_4 X R B | q_a ___________________________________________ I ran 0010, 001110, 00111100, 001100, 0110,010, and 01100 as inputs. The machine gave the correct response in all cases. What case did I forget to check? ------------------------ Yahoo! Groups Sponsor --------------------~--> Get fast access to your favorite Yahoo! Groups. Make Yahoo! your home page http://us.click.yahoo.com/dpRU5A/wUILAA/yQLSAA/GFYolB/TM --------------------------------------------------------------------~-> Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/comp-sci-theory/ <*> To unsubscribe from this group, send an email to: comp-sci-theory-unsubscribe@yahoogroups.com <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/