Intro to NLP Quiz 1: 27 October 2024 (September 2024 term)

In a whimsical language where adjectives change based on the weather, an FST is designed to transform “happy” into “happyrain” on rainy days and “happysun” on sunny days. If the FST has 5 states for “happy” and 3 states each for weather conditions, what’s the minimum total number of states required?

An FSA recognizes words that begin with "un" and end with "ed". The state transitions are defined as follows:

States:

• $q_0$ (Initial state)
• $q_1$ (After 'u')
• $q_2$ (After 'n')
• $q_3$ (After 'e')
• $q_4$ (After 'd', accepting state)

Transitions:

• From $q_0$ on 'u', go to $q_1$
• From $q_1$ on 'n', go to $q_2$
• From $q_2$ on any other character, stay in $q_2$
• From $q_2$ on 'e', go to $q_3$
• From $q_3$ on 'd', go to $q_4$ (Accepting state)

For which of the following inputs will the FSA reach the accepting state?

An FSA recognizes binary strings that end with '01'. The state transitions are defined as follows:

States:

• $q_0$ (Initial state)
• $q_1$ (After '0')
• $q_2$ (After '1', accept state)

Transitions:

• From $q_0$ on input '0', go to $q_1$
• From $q_1$ on input '1', go to $q_2$ (accepting state)
• From $q_2$ on input '0', go back to $q_1$
• From $q_2$ on input '1', stay in $q_2$

What is the output of this FSA for the input string "1101"?