search

StonyBrook-Lin637-S20 / main

Official course website for Compuational Linguistics 2 (LIN 637), Stony Brook University, Spring 2020
3 stars 3 forks source link

Homework 4 #13

Open thomas--graf opened 4 years ago

thomas--graf commented 4 years ago

Link: https://github.com/StonyBrook-Lin637-S20/homework4 Due: Saturday, April 18, 11:59pm Tuesday, April 21, 11:59pm Thursday, April 23, 11:59pm

This is a long exercise, in particular if you do all the optional exercises. Get started on this soon, and make sure you've looked at it before Tuesday so you can ask questions during the Q&A session.

thomas--graf commented 4 years ago

I'm extending the deadline for this homework to Tuesday, April 21, 11:59pm (see the post below).

As so often when I design new exercises, I got carried away and focused on what kind of programming tasks I'd find fun, rather than what can be feasibly accomplished based on what we talked about in class. I've gotten quite a few questions about the RTN recognition method, so it's probably best if we discuss this in depth on Tuesday.

I've also added some extensive pointers as a Github issue in the homework4 repository.

thomas--graf commented 4 years ago

I'm extending the homework one more time, to Thursday, April 23, 11:59pm. In addition, you may assume for the accept and trace method that the RTN is very restricted:

  1. There is exactly one initial state for every subautomaton.
  2. Final states of subautomata never have any outgoing transitions.
  3. If a state has an outgoing transition labeled with the name of a subautomaton, then it has no other outgoing transitions. In other words, the only way to have more than one transition leaving a state is if all the transitions are labeled with distinct "terminal" symbols, not names of subautomata.