../

Morphology and Finite State Automata

Question 1: What is morphology

Morphology is the study of words and how they are formed. Words are the basic building blocks in a syntactic sense But most words can be broken down even further into components such as root, prefix, suffix etc… These component that can’t be broken even further are know as morphemes

Question 2: Give the two types of word classes

  • Open Class
  • Function Class

Question 3: What are the types in open class

  • Nouns
  • Verbs
  • Adjectives
  • Adverbs

Question 4: What are the types in function class

  • Prepositions
  • Conjunctions
  • Determiners

Question 5: What are the problem with counting words

  • Compound words
  • Some languages don’t have word boundaries
  • Clitics

Question 6: What are proclitics and give an example

Clitics that attach to the front of a host Example: ’tis -> it is

Question 7: What is enclitics and give an example

Clitics that attach to the back of a host Example: she’s -> she is

Question 8: Give an example where both type of clitic appear in the same word

’tis’nt -> it is not

Question 9: What are inflections

Different word-forms of the same lexeme

Question 10: What are derivations

New words are formed from existing words

Question 11: Inflection vs Derivations

  • Inflections don’t change the semantics. They usually just change the grammatical category.
  • Derivation change the meaning of the word
  • Example:
    • cat -> cats. There is no meaning change. Both refer to cat
    • happy -> unhappy. These are two contrasting ideas. The meaning has changed

Question 12: Give four inflectional rules for English

  • Tense inflection(verb)
    • walk -> walks -> walked -> walking
  • Number inflection(noun)
    • dog -> dogs
  • Possessive inflection(noun)
    • library -> library’s
  • Pronoun inflection
    • him -> her -> them -> us -> me

Question 13: Give 5 morphological rules for English

  • Adj + -ness
  • V + -er
  • N + -ation
  • Adjectization
    • N + -al
    • V + -able
  • Negation
    • un + adj/verb

Question 14: What are stems and affixes

Stems are the root words Affixes are additions to the root form to form a new word

Question 15: What are the types of affixes

  • Prefix (Before the stem)
  • Suffix (After the stem)
  • Infix (Inside the stem)
  • Circumfixes (surround the stem)

Question 16: Give an English example for each type of affixes

Prefix: Unhappy Suffix: Happiness Infix: No true infixes in the formal language. But colloquially they are usually used in expletives like “beni-fucking-hana” Circumfix: enlighten

Question 17: What are morphemes

Smallest meaningful part of a word

Question 18: What are the two type of morphemes

  • Free Morphemes
  • Bound Morphemes

Question 19: Give examples for some irregular morphemes

  • Irregular plural morphemes
    • Regular plural: dog -> dogs
    • Irregular plural: child -> children
  • Irregular past tense
    • Regular past: walk -> walked
    • Irregular past: leap -> leapt

Question 20: What are allomorphs?

Have the same underlying morpheme but different realization

Question 21: Give an example for allomorph?

Plural allomorph - bus-es - cat-s Both of these belong to the Plural morpheme. But they are realized using different affixes

Question 22: Is morpheme concrete?

No. Morphemes are abstract categories

Question 23: Formally define a Language

Let $\Sigma$ be the set of symbols. A string $\omega$ is defined as a sequence of symbols from $\Sigma$. An empty string is one without any symbols and is denoted as $\epsilon$. A Kleene closure is an infinite set of all the string that can be generated from $\Sigma$. It is denoted by $\Sigma^$. A language $\mathcal{L}$ over $\Sigma$ is defined as a subset of $\Sigma^$

Question 24: What is an automaton?

Automaton is an abstract model of a computer. It consumes an input string and changes its internal state accordingly. It can either accept or reject an input string. The set of string accepted by an automaton is defined as the Language of that automaton

Question 25: Map the different types of automaton and the languages defined by them

Automaton Language
DFA Regular
DPDA CFL
TM Recursively enumerable Languages

Question 26: Formally define a FSM

$M = <Q, \Sigma, q_0, F, \delta>$ Q is the set of all the states(finite) $\Sigma$ is the alphabet(set of symbols) $q_0 \in Q$ is the initial state $F \subseteq Q$ are the final states $\delta: Q \times \Sigma \rightarrow Q$ is the transistion function