Finite State Automata and Transducers

Question 1

Describe a Finite State Automata

Answer 1

A different way to describe regular expressions

An FSA has:

• A finite set of states
• A finite input alphabet
• One start state
• A set of final states
• Transitions

Question 2

The Uses of a Finite State Automata

Answer 2

Use to:

• Generate a string
• Test a string (look at letters on the tape) and accept or reject - if the branch doesn’t end in a final state, the string is rejected

Question 3

How a Finite State Automata Works

Answer 3

• Start in the start state, S0
• The current letter is the first letter on the tape, X
• If the current state has a transition for the letter X to state S1, then new current state is S1, new current letter is the next letter on the tape
• Else, if no transition from the current state for letter X, reject

Question 4

Formal Language

Answer 4

The collection of strings accepted by an FSA

Question 5

Non-Deterministic Finite State Automaton

Answer 5

There can be more than one transition for a given letter

If there is some way to get to the final state, then accept

Equivalent to a Finite State Automaton

Question 6

Morphological Parsing

Answer 6

Analyze and generate text

Create plurals, prefixes, verb endings, etc.

Map one string (lexical: cat +n +pl) to another (surface: cats) - use Finite State Transducer

Question 7

Finite State Transducer

Answer 7

An FSA that reads form one tape and writes to another