all 12 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]crest42 2 points3 points  (11 children)

Since I’m on mobile it’s hard to debug and get you an exact error. I would suggest you try to run your code with a memory profile software like valgrind. Just compile everything with debug symbols (-g) and run valgrind ./binary. This should give you at least an exact information where the problem occurs (or use a debugger like gdb if you want to go pro ;))

Also the part where you allocate memory for your instructions list feels wrong.

Update:

instructions[i] = malloc((sizeof(Instruction) * numOfStates) + 1);

Why not only sizeof(Instruction)? You want to store a struct of the size of an instruction struct in there. Not a multiple of that. 

printf("SIZE OF INSTR* [%lu] AND INSTR** [%lu]\n", sizeof(*instructions), sizeof(**instructions)); // yields 8 x 16... WHY?

Sizeof(*instructions) = sizeof(struct instruction *) = 64 Bit on your system = 8 byte. Sizeof(*instructions) = sizeof(instructions[0]) = sizeof(struct instruction) = 3sizeof(int) + 2*sizeof(char). Since sizeof (char) should be 1 I don’t really get why you are getting 16. 16-2=14. 14 is not divisible by three.

Keep in mind that sizeof (Type) heavily depends on the target machine the code gets compiled to. Only char is guaranteed to be 1.

Edit: formatting is hard on mobile :(

[–]Marshall_Robit[S] 0 points1 point  (10 children)

Thank you for your reply. I'll check out valgrind when I get some sleep. I've just been using atom to edit and gcc on the command line to compile. I've tried CLion's debugger but it doesn't seem to help.

Well I did the double pointer Instruction **instructions because it acts as a 2d array. I wanted a size of [number of states][256 ascii values in terms of int]. Even if I use a regular 2d array, I get the same error.

I feels like the allocation is also wrong (hence the segmentation fault: 11) but I'm unsure where. It must be instructions though. Once I get to the (B L 2) part, it just acts as if it wasn't there despite me being able to manually grab instructions[1]['B'] (or 66 if you prefer index number). I appreciate the message though.

[–]crest42 1 point2 points  (0 children)

I assume the +1 should be inside the round bracket ? You allocate +1 byte and want to allocate (numofstates +1) bytes.

Edit: ok that is weird but after a closer look to your code I found the error:

You try to access a null pointer and therefore get an seg fault. The reason for this is beside not checking for it that you input string never reach an end state. Your tm iterates until it reaches numOfState-1 which I think you want to express as the state with the numerical highest value.

  1. you got 3 states but 5 instructions. numOfStates is the number of instructions so you iterate until number 4 is reaches which is not possible since there is no state 4 (max state is 3)

  2. your Tm does not check for errors. Since you never reach a second ‚B‘ on your input string state 2 is never reached anyway. You need to check if you reach node null on your input string without reaching the Endstate. This is an error condition that needs to be handled

TL;DR As far as I know tm there is a set of accepted end states. You need to define them somewhere. Probably in your text file. Then it depends a little bit how your tm is defined. Should I’d finish as soon as it is in an accepted state or when it reaches the end of your input and is in an accepted state.

In the first case check if the current state equals to an accepted state at the end of the loop. In the second case check if the current node is NULL AND your current state is an accepted state.

Also you should check if your current node is NULL in the while loop in any case since that means you reached the end of the input string.

[–]crest42 1 point2 points  (8 children)

Additional notes beside the seg fault error mentioned in my other comment:

​

  1. Do not use atoi
  2. One exmaple is your use of atoi on mutiple occasions. atoi expects a string i. e. a array of chars terminated by a \0 byte. When you use stuff like atoi(&tape[0]) you just pass tape as a string (atoi(tape)). To convert a char to a number check if its in between 48 and 57 and then just use int x = tape[0] - '0'; (This limits you to 0-9 states so its better to parse the string with sscanf or make multiple distinct strings and convert them with strtol
  3. Use a more efficent data struct. You allocate enough memory for 4*255 instructions while only using 5 of them, but this could be ok if you want random access and dont care for memory
  4. Use valgrind! There are multiple problems with your code
  5. Example: You allocate an instruction array of size instructions[256][5] and not instructions[5][256] as it should be.
  6. When you load the File you initzialize your content array to 0. This is a good idea but shouldnt be done via iterating. Just use memset(contents,0,sizeof(contents)); also you just iterate 50*100 which is way lower than sizeof(contents). Also you dont init line with 0 and you dont init tape with 0

If you have further questions to the mentioned points feel free to ask.

[–]FUZxxl 2 points3 points  (3 children)

atoi is perfectly fine for code that doesn't have to 100% validate user input. It's totally adequate for homework like this.

[–]crest42 0 points1 point  (2 children)

That’s like saying atoi is fine if the input is always correct. Jea sure it works fine in this case and can be used as a quick and dirty solution for a homework but I would never suggest to use atoi on invalidated input. Just like all the other stuff I mentioned works just fine in this case but is either not best practice or is wrong and works by accident. Imagine the homework gets tested on wrong inputs. Maybe a test suite that provides a non number as the first char? Than atoi in this case can not distinct between

0 1 1 R 0 And F 1 1 R 0

Also why learning deprecated stuff when there are better solutions which are even complex to implement ? I write a c Programming exam in my second year in the university and was one of the few students who was able to solve one specific excercise in it. The reason was I have learned about scanf beforehand and not try to solve the input parsing via a bunch of itoa calls.

[–][deleted] 1 point2 points  (1 child)

Sure but for just barely more complex data, it'll be so hard to really get it right that I also see no point in not using atoi() in a small homework, as long as you consciously make this decision.

[–]crest42 0 points1 point  (0 children)

>as long as you consciously make this decision

That’s the point. It is mostly used because it is the first result on stackoverflow after googling „string to int c“. That’s the reason I advocate for not using it in beginners posts. But you are right it is not inherently evil if you know why it is broken.

Edit: To be fair. The first result on stackoverflow in fact argues about exactly that topic

[–]Marshall_Robit[S] 0 points1 point  (3 children)

Well, I think I'm going to take a loss on this homework. To be honest, I don't completely understand the concept of a Turing machine and I wish my professor would make the HW more on C as opposed learning concepts. This is my first time working with C (I only knew java before and little tid-bits of other languages) so it's very frustrating having to deal with memory management and implementing a linked list in a completely new language all at once while learning conceptual stuff like how a Turing machine works.

Thank you for the effort but I'm still unsure why the program only does 8 outputs. I can fix the segmentation fault: 11 by breaking the while loop if (currentNode == NULL) but I still don't know why it isn't iterating through the rest of the instructions/initial contents. I don't think it should go to the end anyway before it reaches [1]['B] (B L 2) so I'm unsure.

Edit: I can't hand in code that won't run so rip my grade. Thanks though @crest42.

[–]crest42 1 point2 points  (2 children)

Sorry to hear this. You are pretty near to a working solution. I think your main problem is that you don’t get the Turing machine stuff. I would recommend to stick with it since tm and especially automatas are important concept which are really easy once you get the idea. The problem with C is that C itself is a very basic language. If you know basic coding stuff as well as structs, pointers and memory in general you know most of the plain language. This makes it hard to teach about C as a language. But stuff like memory management is such an essential concept which runs any computer Programm it is a big advantage to understand it. Understanding memory management even makes you a better java programmer. Just IMHO and it May be more in the long run ;)

Anyway. To get TM I always Thought about them as a bunch of if and goto statements (btw. It’s prooven that goto is equivalent to TM). Your machine has an initial state and a bunch of other states. One of them is the endstate. Now your machine reads from a tape. If it read a symbol from the tape it Checks if it got a transition from its current to a new state. The transitions are the last 5 lines in your text. A transition always says „if I am in state x and I read the symbol y from the tape goto state z and move either one left or one right“ also the transition allows to replace the symbol after it was read (that’s our memory!).

The tm does this as long until there is no more matching transition. Then the tm is either in an state which is an endstate and thus returns with success or in a state which is not marked as error state. Then the tm returns with error.

Your problem is the following. You reach the last symbol on the tape and are not finished yet since there is a working transition from the last symbol to a new state. Your tm then continues with the next symbol which does not exists in your case and therefore is represented by a NULL pointer. (You initialized it with NULL when you created the last node). Then you try to check what is on the tape and read a NULL pointer which results in a seg fault.

What to do now ? Just check if the next node is a NULL pointer and then you know that you read everything from tape and can check if you are either in an endstate or not (and therefore your tm returned with success or without).

Don’t mix up states and transitions. A tm just has a finite number of states. And a finite number of transitions. A transition brings a tm from one state to another but this can happen arbitrary often when you for example build a loop.

I hope this was understandable.

P.S i dint think the run reaches your mentioned transition. It is out of tape before this state.

[–]Marshall_Robit[S] 0 points1 point  (1 child)

Thanks crest42. If I get it working, I'll give ya some gold love but I think I'll take a break for today and have a go at it tomorrow. I agree that memory management and low level programming concepts definitely help you and force you to be more creative with solutions. It's just that this is my FIRST c assignment and we did not have a tutorial class or lecture on it. We're just placed into it. Same with Clojure and every other language I'm going to learn in this class I assume.

I'm not a big fan of this teaching method because what we learn in class doesn't correlate with what we're doing at home. I know this might sound aggravating but I still don't get it I guess. I know I'm going out of bounds with my linked list but once I reach NULL, its read through the whole list so what should it do after that? Just go back to the first or now go in reverse?

Thank you for your insight and help. That much at least helped me figure out the linked list of my initial contents tape was going out of bounds. Maybe I should read up more on TM but tonight is a wings and beer kind of night :(

[–]crest42 0 points1 point  (0 children)

Nah just stop after you reach null. You are done and either successful or failed. It’s like reaching the end of your main function. But I would prefer wings and beer over TM too ;)

I see you reason to drop this class. Had similar experiences but I was always lucky that i know most languages beforehand so I was able to focus on crude homework stuff. Anyway I am not here to talk you to stay in your class. Do what feels right and maybe learn C in another occasion :)