..

Morphology and Finite State Automata

[!question]- 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]- Give the two types of word classes

  • Open Class
  • Function Class

[!question]- What are the types in open class

  • Nouns
  • Verbs
  • Adjectives
  • Adverbs

[!question]- What are the types in function class

  • Prepositions
  • Conjunctions
  • Determiners

[!question]- What are the problem with counting words

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

[!question]- What are proclitics and give an example Clitics that attach to the front of a host Example: ’tis -> it is

[!question]- What is enclitics and give an example Clitics that attach to the back of a host Example: she’s -> she is

[!question]- Give an example where both type of clitic appear in the same word ’tis’nt -> it is not

[!question]- What are inflections Different word-forms of the same lexeme

[!question]- What are derivations New words are formed from existing words

[!question]- 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]- 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]- Give 5 morphological rules for English

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

[!question]- What are stems and affixes Stems are the root words Affixes are additions to the root form to form a new word

[!question]- What are the types of affixes

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

[!question]- 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]- What are morphemes Smallest meaningful part of a word

[!question]- What are the two type of morphemes

  • Free Morphemes
  • Bound Morphemes

[!question]- 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]- What are allomorphs? Have the same underlying morpheme but different realization

[!question]- 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]- Is morpheme concrete? No. Morphemes are abstract categories

[!question]- 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]- 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] Map the different types of automaton and the languages defined by them

Automaton Language
DFA Regular
DPDA CFL
TM Recursively enumerable Languages

[!question]- 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