Computer Science 4750, Fall '25
Potential Exam Questions

---

Copyright 2025 by H.T. Wareham
All rights reserved

---

Topic 1. Topic 2, Topic 3, Topic 4,` Topic 5, Topic 6

Questions prefixed by "(*)" involving executing one or more of the algorithms discussed in class.

Topic #1 (Course introduction; Lecture #1)

• What are the two ``flavors'' of NLP as discussed in class?

Topic #2 (The Characteristics of Natural Language; Lecture #2-5)

• What are three of the subdisciplines of linguistics discussed in class? Please indicate the order of these areas with respect to speech recognition, and for each subdiscipline, list the linguistic entities that are operated on by the processes proposed by that subdiscipline.
• What are the two types of phonetics discussed in class?
• What are the two basic types of morphemes?
• What are four of the types of affix morphemes discussed in class?
• What, from the viewpoint of linguistics, are the three basic types of mechanisms required to implement NLP?
• What are the two broad classes of linguistic process-systems?

Topic #3 (NLP Mechanisms: Finite-state grammars, automata, and transducers; Lecture #5-9)

• What are three of the four finite-state mechanisms discussed in class that are used in natural language processing?
• What is the general form of a production rule in a finite-state grammar?
• What are the two basic operations for a regular grammar or a FSA?
• What are the two main types of FSA discussed in class?
• (*) Given an NFA, circle all of the words in a given set that are accepted by this NFA. the following non-deterministic Finite-state
• (*) Given two DFA D1 and D2 that recognize string-sets S1 and S2, give the FSA DR that recognizes the concatenation / union / intersection of S1 and S2 as created by the constructions described in class. Note that DR should include all states and transitions created during the appropriate construction method.
• What are the three basic operations for a FST?
• (*) Given a FST and a lower (upper) string l (u), reconstruct all upper (lower) strings u (l) such that the string-pair l/u is accepted by the FST above.
• What are the three operations on pairs of FSA for which algorithms were given / discussed in class?
• What are the two operations on pairs of FST for which algorithms were given / discussed in class?

Topic #4 (NLP Mechanisms: Context-free grammars; Lecture #9-12)

• What is the general form of a production rule in a context-free grammar?
• What are the two basic operations for a context-free grammar?
• What makes a context-free grammar ambiguous?
• Given a context-free grammar G and a sentence S, draw a derivation-tree for S relative to G.
• Is the context-free grammar G given in the previous question ambiguous relative to sentence S? Answer ``Yes'' or ``No''.
• Is the context-free grammar G given in the previous question ambiguous relative to sentence S? If not, write ``No''. If so, draw a different derivation-tree for S relative to G than the one you gave previously.
• What are the two types of search implemented in context-free grammar parsing algorithms?
• What are two of the non-probabilistic context-free grammar parsing algorithms discussed in class? For each algorithm, state whether it is a top-down or bottom-up parsing algorithm.
• Given an Extended Chomsky Normal Form context-free grammar G and a sentence S, execute the CKY algorithm on S relative to G to fill in all valid constituents in a given table. Once this is done, circle the appropriate constituents and link them by traceback arrows to indicate how the derivation-tree given in the previous question can be reconstructed from your filled-in table.
• Given a probabilistic context-free grammar G and a sentence S, draw a derivation-tree for S relative to G and compute the probability of this derivation-tree relative the simple model of probability assignment discussed in class.
• Given an Extended Chomsky Normal Form context-free grammar G and a sentence S, draw a derivation-tree for S relative to G.

Topic #5 (NLP Mechanisms: Neural networks; Lecture #13-14)

• What is the general structure of an artificial neuron?
• What is the general structure of a multi-layer feed-forward neural network?
• What are three of the types of mechanisms for dealing with overfitting discussed in class?
• What are three of the neural-network architectures discussed in class?
• What are three of the types of recurrent neural networks discussed in class?

Topic #6 (NLP Applications; Lecture #15-17)

• What are three of the four types of partial morphological and syntactic parsing discussed in class?
• What is the commonly-used semantic representation formalism discussed in class?
• What are the two types of multi-utterance discourses discussed in class?
• What are the two types of restricted SDS discussed in class that maintain the illusion of dialogue while having the minimum underlying mechanisms for modeling common ground or dialogue narrative?
• What are the two schools of thought within the language acquisition community in linguistics?
• What are three of the four types of spelling errors discussed in class?
• What are two types of spelling-related NLP problems discussed in class?
• What are the three types of automated machine translation discussed in class, and how are they related by the Vauquois Triangle?