Computational Morphology

Question 1

What is a Finite State Machine’s “emission”?

Answer 1

Letters produced at each transition

Question 2

What is a Finite State Machine’s formal language?

Answer 2

The set of strings that can be generated while moving from a start state to an end states. Transitioning between states emits symbols of the string. This is the same as the set of strings that can be recognized by matching input symbols with emissions by taking valid transitions from start state to finish state.

Question 3

Are the languages of Finite State Machine’s finite or infinite?

Answer 3

They can be either.

Question 4

What are “regular languages”

Answer 4

Languages that can be produced by finite state machines or regular expressions. They are usually assumed sufficient to describe phonology and morphology.

Question 5

Give an example of an irregular language

Answer 5

aⁿbⁿ

Question 6

Apart from finite state machines. What other way can regular languages be expressed?

Answer 6

Using regular expression.

Question 7

What classes of formal languages did Chomsky describe? (4)

Answer 7

3- Regular

2 -context-free

1 - context-sensitive

0 -recursively enumerable

Question 8

What is a recursively enumerable language?

Answer 8

Anything a computer program can produce

Question 9

What is the Chomsky Hierarchy

Answer 9

Languages further down the list of formal languages become.

• increasingly difficult to compute
• capable of describing more languages

Regular < Context-free < Context-Sensitive < Recursively Enumerable.

Question 10

Difference between a non-deterministic and deterministic FSM

Answer 10

Multiple transitions are possible from an input at each state. AN input is accepted as long as it produces an ordinal set of transition that finishes at an accept state