Building Structure while RecognizingIn the previous chapter, we learned that finite state recognizers are machines that tell us whether a given input is accepted by some finite state automaton. We can give a word to a recognizer and the recognizer will say ``yes'' or ``no''. But often that's not enough: in addition to knowing
that something is accepted by a certain FSA, we would like to have an explanation of
why it was accepted. A
↗finite state parser gives us that kind of explanation by returning the sequence of transitions that was made.This distinction between
↗recognizer s and
↗parser s is a standard one: Recognizers just say ``yes'' or ``no'' while parsers also give an analysis of the input. It does not only apply to finite state machines, but also to all kinds of machines that check whether some input belongs to a language, and we will make use of it throughout the course.
Answer ``true'' or ``false'' to the following questions:
- It is possible to write a finite state automaton (FSA) to generate/recognize any formal language.
- It is not possible to write an FSA that generates/recognizes the formal language anbn.
- It is not possible to write an FSA that generates/recognizes the formal language anbm.
- We can generate more languages using non-deterministic finite automata than we can using deterministic finite automata.
- A finite state transducer (FST) is essentially an FSA that works with 2 (or more) tapes.
Write an FST that transduces between strings of as (of length m), and strings consisting of a c, followed by mbs, followed by another c. For example, your FST should transduce between aaa and cbbbc. Write down your FST in both graphical and Prolog notation.
Write an FST that, given a string of as, bs, and cs, deletes all the as, turns the bs to ds, and leaves the cs alone. For example, given the input abbaabcbca, your FST should transduce return dddcdc. Write down your FST in both graphical and Prolog notation.
Design an FST that transduces number names in written form between two languages you know (for all numbers from 0 to 100). For example, if you write a French_English FST, this should transduce between `ninety four' and `quatre vingt quatorze', and if you write a Dutch_German FST, this should transduce between `een en twintig' and `ein und zwanzig'. You have seen a similar transducer in
» What are Finite State Transducers?.
In Lecture 1, we claimed that the formal language anbn was relevant to natural language, because natural languages contain various ``balanced'' syntactic constructions. Give an example from some natural language you are familiar with (German, Irish, Russian, French, English, Japanese, Chinese, Tagalog,...). Make sure you explain why your answer is relevant.