Info2 Sommersemester 2015

Website of Prof. Dr. Barne Kleinen, Professor for Media Informatics (Bachelor/Master) at HTW Berlin

Info2: Exercise 11: Finite State Automata and Sorting Algorithms

     <prev next>

Pre-Lab

No Pre-Lab this time.

Assignment

Part 1: Finite Automata

This is to get some practice with Finite Automata.

Which Languages do these Automata accept?

For the following two Finite Automata given by their transition tables, draw the transition diagram and describe the language they accept in English (or German) sentences. Give examples for words in and not in the language.

You find a NFA Simulator in https://github.com/htw-imi-info2/Lab11_DFA. Create Simulations for them with test cases from the words you found. You can use NFA1AtThirdFromLast.java as an example.

Automaton A

Start state: q0, accept state: q0

01
q0q0q1
q1q2q3
q2q0q1
q3q2q3
Automaton B

Start state: q1, accept states: q2, q4

01
q1q2q4
q2q1q3
q3q4q2
q4q3q1

Design Finite Automata

Give transition diagrams for the following three Finite Automata, define testcases and test your automata by using the simulator above. Again, you can use NFA1AtThirdFromLast.java as an example.

  1. Design a Finite Automaton that accepts all strings of 0’s and 1’s not containing 010 as a substring.
  2. Design a Finite Automaton that accepts all strings with at most one pair of consecutive 0’s and at most one pair of consecutive 1’s.
  3. Design a Finite Automaton that accepts the language of all Strings of 0 and 1s, that when interpreted as a binary number, are divisible by three.

Part 2: Sorting

Generate an array containing 10 random integers between 1 and 100 and perform manual walkthroughs for 3 out of the 5 given sorting algorithms per person. Try to cover as many sorting algorithms as possible within your teams.

Use the exact algorithms git sfrom this repository: https://github.com/htw-imi-info2/Lab11_Sorting Each of them has a location marked with //step. Note down the state of the array at this location for each time the algorithm passes this line.

Lab Report / What to turn in

Your report is due the day before your next lab (for exact times, please refer to moodle).

Submit a Report in PDF Format and the Source Code (of the FA Simulations) as a zipped file.

Please report in your report how long you worked on each exercise.