据我所知它可以工作。它并不出色，并且Turing机在此早期版本中进行了硬编码，但是可以使用。
我真的很想对代码进行一些检查。我特别好奇的一件事是，我是否正在执行适当的错误检查和处理。例如在某些情况下，
assert更合适还是我应该做更多错误检查？#ifndef __turing_h__
#define __turing_h__
#define MAX_TRANSITIONS 5
#define MAX_STATES 25
// forward declare structs
struct State;
struct Transition;
typedef enum {
LEFT, RIGHT
} Direction;
typedef enum {
FALSE, TRUE
} Bool;
struct Transition {
char input;
char write;
Direction move;
struct State *next;
};
typedef struct Transition Transition;
struct State {
int id;
int trans_count;
struct Transition* transitions[ MAX_TRANSITIONS ];
Bool accept;
Bool reject;
};
typedef struct State State;
struct Turing {
int state_count;
State* states[ MAX_STATES ];
State* current;
int head;
};
typedef struct Turing Turing;
#endif
turing.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "turing.h"
// disable debug mode
#define NDEBUG
#include "debug.h"
// used to hand out ids
int state_id = 0;
void die( char *message )
{
if( message )
{
printf( "Error: %s.\n", message );
}
// exit unsuccesfully
exit(1);
}
Transition* Transition_create( char input, char write, Direction move, State *next )
{
// allocate memory
Transition *trans = malloc( sizeof( Transition ));
if( ! trans ) die( "Memory error" );
trans->input = input;
trans->write = write;
trans->move = move;
trans->next = next;
return trans;
}
void Transition_destroy( Transition* trans )
{
free( trans );
}
State* State_create( Bool accept, Bool reject )
{
// allocate mem
State *state = malloc( sizeof( State ));
if( ! state ) die( "Memory error" );
state->id = state_id++;
state->accept = accept;
state->reject = reject;
state->trans_count = 0;
return state;
}
void State_add_transition( State *state, Transition *trans )
{
// check if we can still add another transition
if( state->trans_count == MAX_TRANSITIONS ) {
char buffer[ 50 ];
sprintf( buffer, "State %d already has the maximum amount of transitions.", state->id );
die( buffer );
}
// add the transition
state->transitions[ state->trans_count ] = trans;
state->trans_count++;
}
void State_destroy( State *state )
{
int i = 0;
// loop over its transitions
for( i = 0; i < state->trans_count; i++ ) {
Transition *trans = state->transitions[ i ];
if( !trans ) die( "Could not fetch transition." );
Transition_destroy( trans );
}
free( state );
}
Turing* Turing_create()
{
// allocate mem
Turing *machine = malloc( sizeof( Turing ));
machine->state_count = 0;
machine->current = NULL;
machine->head = 0;
return machine;
}
void Turing_destroy( Turing *machine )
{
int i = 0;
// loop over it's states
for( i = 0; i < machine->state_count; i++ ) {
State *state = machine->states[ i ];
if( !state ) die( "Could not fetch turing state" );
State_destroy( state );
}
free( machine );
}
void Turing_add_state( Turing *machine, State *state )
{
if( machine->state_count == MAX_STATES ) {
die( "The turing machine already has the maximum amount of states" );
}
// add the state
machine->states[ machine->state_count++ ] = state;
}
State* Turing_step( Turing *machine, char* tape, int tape_len )
{
int i = 0;
char input = tape[ machine->head ];
State* state = machine->current;
// look for a transition on the given input
for( i = 0; i < state->trans_count; i++ ) {
Transition* trans = state->transitions[ i ];
if( !trans ) die( "Transition retrieval error" );
// check if this is a transition in the given char input
if( trans->input == input ) {
debug( "Found transition for input %c", input );
State *next = trans->next;
if( !next ) die( "Transitions to NULL state" );
// write if nescesary
if( trans->write != '#ifndef __debug_h__
#define __debug_h__
#ifndef NDEBUG
#define debug(M, ... ) fprintf( stderr, "DEBUG: %s:%d: " M "\n", __FILE__, __LINE__, ##__VA_ARGS__ )
#else
#define debug(M, ... )
#endif
#endif
' ) {
debug( "Writing %c", trans->write );
tape[ machine->head ] = trans->write;
debug( "Writing done" );
}
// move the head
if( trans->move == LEFT ) {
if( machine->head > 0 ) {
machine->head--;
debug( "Moved head left" );
}
} else {
if( machine->head + 1 >= tape_len ) {
die( "Machine walked of tape on right side" );
}
machine->head++;
debug( "Moved head right" );
}
// move the machine to the next state
debug( "Setting current state" );
machine->current = next;
return next;
}
}
char buffer[ 50 ];
sprintf( buffer, "Turing machine blocked: state %d for input %c", state->id, input );
die( buffer );
}
void Turing_run( Turing *machine, char *tape, int tapelen )
{
// check if the start state is configured properly
if( !machine->current ) die( "Turing machine has now start state" );
while( TRUE ) {
State* state = Turing_step( machine, tape, tapelen );
if( state->accept ) {
printf( "Input accepted in state: %d\n", state->id );
break;
} else if( state->reject ) {
printf( "Input rejected in state: %d\n", state->id );
break;
} else {
printf( "Moved to state: %d\n", state->id );
}
}
}
int main( int argc, char* argv[] )
{
Turing* machine = Turing_create();
State* q1 = State_create( FALSE, FALSE );
State* q2 = State_create( FALSE, FALSE );
State* q3 = State_create( FALSE, FALSE );
State* q4 = State_create( FALSE, FALSE );
State* q5 = State_create( FALSE, FALSE );
State* qaccept = State_create( TRUE, FALSE );
State* qreject = State_create( FALSE, TRUE );
Transition* q1_r_space = Transition_create( ' ', 'L = { 0^2^n | n > 0 }
', RIGHT, qreject );
Transition* q1_r_x = Transition_create( 'x', 'q4312078q', RIGHT, qreject );
Transition* q1_q2_zero = Transition_create( '0', ' ', RIGHT, q2 );
Transition* q2_q2_x = Transition_create( 'x', 'q4312078q', RIGHT, q2 );
Transition* q2_a_space = Transition_create( ' ', 'q4312078q', RIGHT, qaccept );
Transition* q2_q3_zero = Transition_create( '0', 'x', RIGHT, q3 );
Transition* q3_q3_x = Transition_create( 'x', 'q4312078q', RIGHT, q3 );
Transition* q3_q4_zero = Transition_create( '0', 'q4312078q', RIGHT, q4 );
Transition* q3_q5_space = Transition_create( ' ', 'q4312078q', LEFT, q5 );
Transition* q4_q3_zero = Transition_create( '0', 'x', RIGHT, q3 );
Transition* q4_q4_x = Transition_create( 'x', 'q4312078q', RIGHT, q4 );
Transition* q4_r_space = Transition_create( ' ', 'q4312078q', RIGHT, qreject );
Transition* q5_q5_zero = Transition_create( '0', 'q4312078q', LEFT, q5 );
Transition* q5_q5_x = Transition_create( 'x', 'q4312078q', LEFT, q5 );
Transition* q5_q2_space = Transition_create( ' ', 'q4312078q', RIGHT, q2 );
State_add_transition( q1, q1_r_space );
State_add_transition( q1, q1_r_x );
State_add_transition( q1, q1_q2_zero );
State_add_transition( q2, q2_q2_x );
State_add_transition( q2, q2_a_space );
State_add_transition( q2, q2_q3_zero );
State_add_transition( q3, q3_q3_x );
State_add_transition( q3, q3_q4_zero );
State_add_transition( q3, q3_q5_space );
State_add_transition( q4, q4_q3_zero );
State_add_transition( q4, q4_q4_x );
State_add_transition( q4, q4_r_space );
State_add_transition( q5, q5_q5_zero );
State_add_transition( q5, q5_q5_x );
State_add_transition( q5, q5_q2_space );
Turing_add_state( machine, q1 );
Turing_add_state( machine, q2 );
Turing_add_state( machine, q3 );
Turing_add_state( machine, q4 );
Turing_add_state( machine, q5 );
Turing_add_state( machine, qaccept );
Turing_add_state( machine, qreject );
machine->current = q1;
char* input = "0000000000000000 ";
int len = strlen( input );
char* tape = malloc( len * sizeof( char ));
strcpy( tape, input );
Turing_run( machine, tape, len );
// clean up
Turing_destroy( machine );
free( tape );
}
debug.h
q4312078q
目前，模拟器已配置为接受来自该语言的输入字符串：
q4312078q
或者：所有长度为2的幂的0字符串。
碰巧有Sipser计算理论导论。它在第2版的第145页上。
GIT存储库和相关文档（我们有一个基本用法的小型Wiki）
#1 楼
AJ，我喜欢。编码非常好。这里有一些评论。我已经省略了@LokiAstari已经提到的内容
不需要对
struct Transition进行前向声明。die，更喜欢将错误打印为stderr exit(1)更喜欢exit(EXIT_FAILURE) 一些杂乱的注释（“退出失败”，“分配内存”等）
State_create不会初始化transitions（可能是良性的）sprintf经常使用不当，导致缓冲区溢出。优选snprintf。但是，由于仅在临死前使用它，所以没有风险。Turing_create不会检查malloc（其他用途是）。您喜欢
type* var还是type *var？我更喜欢后者，但是无论使用哪种方式，一致性都是最好的。
在某些地方，您可以在循环中定义循环变量：
Turing_step 使局部函数静态。这是一个好习惯，但对于一个小型项目而言，
没什么区别。
如果对齐，则
for( int i = 0; ...中的Transition_create调用列表将更具可读性。main存在一些问题在复制main时。input返回strlen，而size_t取malloc。因此最好使用size_t（-Wsign-conversion）sizeof（char）根据定义为1
您为字符串副本分配的字节数太少。
您可以使用
size_t（如果有）。但请注意，不必分配
strdup的副本。您只需将字符串声明为input而不是char input[] = "..."即可，它是可写的。如果使用
char* input = "..."，则无需执行char input[]-只需strlen(input) 传递输入字符串的长度似乎是不必要的（
该字符串的用户可以检查终止的'\ 0'）
关于错误检查和使用
sizeof input -1，我认为您已经完成了好好检查。我不是断言的主要使用者（所以也许我对断言的想法对您没有多大用处）。使用断言总是让我感到不安-它们很有趣
。他们说，实际上，被测试的条件是如此重要，以至于如果在测试期间发生它就值得退出，但是如果它在正常使用（NDEBUG）期间发生，则可以忽略。除非您可以确保在测试期间可以检测到所有可能的断言失败，否则这是不合逻辑的。对我来说，
意味着断言仅应用于测试程序固有的错误，而这些错误与程序无关，也不依赖于数据或运行时。
例如，检查
assert是否会失败请使用malloc条件，而仅在算法编码错误的情况下检查可能发生的事情
是对
if的合理使用。在您的情况下，我可能会尝试使用assert来检查数组项是否为NULL： Transition *trans = state->transitions[ i ];
assert( trans );
但是我见过断言像五彩纸屑，所以意见显然不同。也许其他审稿人也可以提供帮助。
评论
\ $ \ begingroup \ $
谢谢。其中一些我已经合并了。我将对其中一些进行研究。对于断言/如果陷入困境，我同意你的看法。我看到很多代码（其他语言）似乎忘记了断言通常不是用于运行时检查的。
\ $ \ endgroup \ $
–A.J. Rouvoet
2012年12月21日上午10:26
\ $ \ begingroup \ $
关于传递字符串的长度：我得到的印象是，对此有多种意见。您要么必须确保所有字符串都被\ 0终止，然后依靠C字符串工具和/或进行额外的检查以防止溢出。您显然会投票赞成前者。还有谁？
\ $ \ endgroup \ $
–A.J. Rouvoet
2012年12月21日上午10:28
\ $ \ begingroup \ $
AJ，字符串应始终以\ 0结尾，但通常数组不应该以\ 0结尾。但是字符串是数组-也许就是混乱的所在...请注意，我在上面纠正了一个严重错误的建议（在指针上使用sizeof！）
\ $ \ endgroup \ $
–威廉·莫里斯（William Morris）
2012年12月21日在12:43
\ $ \ begingroup \ $
不，没有混乱。我只是在考虑是否应该信任程序中的字符串以正确终止它们。我是不是该？
\ $ \ endgroup \ $
–A.J. Rouvoet
2012年12月21日在13:12
\ $ \ begingroup \ $
是的，如果它是由编译器创建的（从引用的字符串，如“ 01234 ..”中）创建，则它肯定会终止。如果是由使用strcpy的人（如您的原始代码）创建的，则取决于代码。但是，如果缺少\ 0，则使用strlen找出它的持续时间也会失败，因为strlen找不到所需的\ 0。因此，在实践中，您必须假定它已正确终止。
\ $ \ endgroup \ $
–威廉·莫里斯（William Morris）
2012-12-21 13:26
#2 楼
具有两个下划线的标识符保留用于实现（因此请不要使用它们）。此外，MACROS（由#define定义的事物）传统上都是大写的（因为它们不遵守范围规则（因为它们不属于范围规则） C语言，但它是预处理器系统的一部分），我们将它们全部大写，以确保我们不会与其他标识符发生意外冲突。）
#ifndef __turing_h__
#define __turing_h__
如果您将要声明它们，然后也进行适当的typedef。
struct State;
struct Transition;
// Add
typedef struct State State;
typedef struct Transition Transition;
现在您可以在不使用前缀struct的情况下进行引用。
不要使用全部大写。宏（没有作用域边界的宏可能会使用这些标识符发挥作用）。
typedef enum {
LEFT, RIGHT
} Direction;
系统头文件aready定义为FALSE / TRUE。同样在这种情况下，您将TRUE定义为1。这是不正确的。关于
TRUE，您唯一可以说的是(!FALSE)。不一定与1.相同。typedef enum {
FALSE, TRUE
} Bool;
这没什么问题。获得最佳包装的安排。始终按从大到小的顺序订购它们（如果您关心布局（通常这不是一件大事，但是如果您有较大的空间需求并且可能会成为问题））。
struct Transition {
char input;
char write;
Direction move;
State *next;
};
所以我会这样布置：
typedef struct Transition {
State *next; // At least as big as an int (but can be bigger).
Direction move; // Enum is an int.
char input; // Now chars.
char write;
} Transition;
评论
\ $ \ begingroup \ $
“不要全部使用大写字母。”实际上，所有大写字母是声明常量，枚举和所有方式的全局标识符的一种非常常见的方式，而不仅仅是宏。
\ $ \ endgroup \ $
–伦丁
2012年12月21日在7:25
\ $ \ begingroup \ $
“ ...您将TRUE定义为1。这是不正确的。”是的，这是完全正确的。始终使代码与C标准布尔类型兼容，后者明确保证为1，而不是一些不可思议的“非0可能为1”。最好当然是使用stdbool.h中的标准布尔类型。
\ $ \ endgroup \ $
–伦丁
2012年12月21日在7:27
\ $ \ begingroup \ $
啊，stdbool.h。另一个有用的提示！
\ $ \ endgroup \ $
–A.J. Rouvoet
2012年12月21日上午10:29
#3 楼
除了其他答案外，我只留下了一个小纸条。您的
#include应当采用不同的组织方式：#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "turing.h"
最好先包含自己的标头，以避免系统库出现任何可能的依赖性问题。换句话说，您不应该强制将标头公开给其他库，尤其是在不希望发生这种情况的情况下。
此外，您可以按一定顺序对标头进行排序，例如按字母顺序。这样可以更轻松地跟踪它们。
#include "turing.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#4 楼
随着malloc（）返回void * ，您必须更正所有内存分配语句
Turing *machine = malloc( sizeof( Turing )); --->
Turing *machine = (Turing*) malloc( sizeof( Turing )); ，等等
评论
\ $ \ begingroup \ $
不，不要那样做。 stackoverflow.com/questions/605845/…
\ $ \ endgroup \ $
–垫子
17年1月21日在10:36
评论
您可能会发现此页面有趣：codegolf.stackexchange.com/questions/8787/…如果您想查看修订后的代码，请问另一个问题。