Theory of Computation

FSA 1 You are in the start state. Select the next bit of your input or click "done" [[zero->First 0]] [[one->FSA 1]] [[done->End Not in Final State]] Stuck? Get a [[hint->FSA 1 Hint 1]]

FSA 1 Select the next bit of your input or click "done" [[zero ->Second 0]] [[one ->FSA 1]] [[done->End Not in Final State]]

FSA 1 Select the next bit of your input or click "done" [[zero->Final State Ready]] [[one->FSA 1]] [[done->End Not in Final State]]

FSA 1 Select the next bit of your input or click "done" [[zero->Final State Ready]] [[one->FSA 1]] [[done->End in Final State]]

FSA 1 Your input did not end in the final state of FSA 1. view the [[answer->FSA 1 Solution]], [[ try again->FSA 1]], or [[quit->ending]]

FSA 1 Hint: This FSA computes the language of all binary representations of natural numbers that are divisible by 8. Zero is represented by "000", one is represented by "001", and so on. Go [[back->FSA 1]] Get second [[hint ->FSA 1 Hint 2]]

FSA 1 Hint 2: A binary number is divisibly by 8 if it ends in three consecutive zeros Go [[back->FSA 1 Hint 1]]

FSA 1 Your input was accepted and ended in the final state! This means your input belongs in the language x, and thus is a binary representation of a natural number that is divisible by 8. A binary number is divisible by 8 if the last 3 bits are zeros. If a one is encountered, you return to the start state and look for three zeroes until the end of the input string. {000, 1000, 10101000, 1111111000} are all examples of valid solutions for FSA 1 [[FSA 1->FSA 1]] [[FSA 2->FSA 2]] [[quit->ending]]

FSA 1 The FSA we were looking for is any binary number input that is divisible by 8. A binary number is divisible by 8 if the last 3 bits are zeros. If a one is encountered, you return to the start state and look for three zeroes until the end of the input string. [000, 1000, 10101000, 1111111000, 10001000] are all examples of valid solutions [[FSA 1->FSA 1]] [[FSA 2->FSA 2]] [[quit->ending]]

FSA 2 You are in the start state. Select the next bit of your input or click "done" [[zero->FSA 2: 0 is starting bit]] [[one->temp]] [[done->FSA 2 End Not in Final State]] Stuck? Get a [[hint->FSA 2 Hint 1]]

Main Menu Make your way through 2 Finite State Automatas (FSAs) by finding a sequence of bits that, when put through the FSA, will end in the final state. You will make it to the final state if and only if your input (sequence of bits) satisfies the requirements of the language x (if your input is part of the language x). The FSAs compute different languages. The FSAs used and language definitions were sourced from Week 6's problem set for the course CS3102: Theory of Computation at the University of Virginia. This Twine representation of FSAs was made by Selena Johnson. The target audience for this is people who have taken CS3102 or those who are familiar with FSAs. [[begin->FSA 1]] [[quit->ending]]

Thanks for playing! Click [[here->FSA 1 Solution]] to view the solution for FSA 1 Click [[here->FSA 2 Solution]] to view the solution for FSA 2 Jump to [[FSA 1->FSA 1]] or [[FSA 2->FSA 2]]

FSA 2 This FSA accepts any sequence of bits that either starts with 1 and is even in length or starts with 0 and is odd in length. See examples [[here->FSA 2 Solution Examples]] [[FSA 1->FSA 1]] [[FSA 2->FSA 2]] [[quit->ending]]

FSA 2 Select the next bit of your input or click "done" [[zero->FSA 2 Final Loop]] [[one->FSA 2 Final Loop]] [[done->FSA 2 End Not in Final State]]

FSA 2 Select the next bit of your input or click "done" [[zero->temp]] [[one->temp]] [[done->FSA 2 End in Final State]]

FSA 2 Your input was accepted and ended in the final state! This means your input belongs in the language x, and thus is a sequence of bits that either started with a 1 and is even in length, or started with a 0 and is odd in length. {011, 1000, 10101000, 0} are all examples of valid solutions for FSA 2 [[FSA 1->FSA 1]] [[FSA 2->FSA 2]] [[quit->ending]]

FSA 2 Your input did not end in the final state of FSA 2. view the [[ answer->FSA 2 Solution]], [[ try again->FSA 2]], or [[quit->ending]]

{011, 1000, 10101000, 0} are all examples of valid solutions for FSA 2 [[back ->FSA 2 Solution]]

FSA 2 You can probably brute force your way through this FSA. Try a few different input strings before viewing the solution [[here->FSA 2 Solution]] [[back->FSA 2]]