Ling484 Notes

A. C. Brett acbrett@uvic.ca Department of Linguistics University of Victoria Clearihue C139

Table of Contents

• Sets and Sentence Analysis
• Specifying a set by listing its members
• Specifying a set by identifying a property of its members
• Identifying a member of a set
• Subset of a set
• Proper subset of a set
• Equality of sets
• Equivalence of sets
• Intersection of sets
• The null set
• Union of sets
• Difference of sets
• Sets of sets
• Sets of words
• Subsets of words
• Finite, infinite, denumerable, and countable sets
• Products of sets
• Ordered pairs
• Ordered pairs and rewriting rules
• Mappings and partial mappings
• Ordered triples and rewriting rules
• Ordered n-tuples and strings
• Strings over a vocabulary
• Length of a string
• Null string
• Concatenation of strings
• Finite concatenative closure
• Closure without the null string
• Partial mappings and sentence analysis
• Derivations and sentential forms
• The derivation relation
• Closure of the derivation relation
• Terminal and non-terminal vocabularies
• Generative grammar
• Language generated by a grammar
• Syntactic Structure Representations
• Lexical Categories
• Syntactic Categories
• Rewriting Rules
• Phrase-Structure Grammar
• Derivation of Sentences
• Context-Free Language
• Tree Diagram
• Bracketed String
• Equivalence of Representations
• Prolog List
• Indented Vertical List
• Character Tree
• Transition Network
• Chart
• Box Diagram
• Procedures and Algorithms
• Procedures
• Algorithms
• Examples
• Chart Parsing
• The Strong Competence Hypothesis
• Phrase-Structure Grammars and the Chomsky Hierarchy
• Phrase-Structure Grammars
• Productions
• Sentences
• Languages
• Equivalent Grammars
• Chomsky Hierarchy
• Hierarchy of Languages
• l-Productions
• l-Free Grammars
• Normal Form Grammars
• Chomsky Normal Form
• Self-Embedding Grammars
• Type 3 Normal Forms
• Finite-State Automata
• Input Tape
• Read Unit
• Control Unit
• Ordered Quintuple Specification
• Transition Function
• Language of the Automaton
• Reductions
• Equivalence to Finite Grammars
• Example
• Transition Network
• Accepting Paths
• Nondeterministic Automata
• Push-Down Automata
• Components of a Push-Down Automaton
• Push-Down Store
• Ordered Sextuple Specification
• Transition Function
• Initial Transition
• Read/Push Transition
• Lambda/Pop Transition
• Configurations
• Reductions
• Language of the Machine
• Equivalence to Context-Free Grammars
• Example
• Acceptance Process
• Transition Network
• Transition Network Grammar
• Recursive Transition Networks
• Arcs and Nodes
• Subnetworks
• NP Subnetwork
• VP Subnetwork
• S Subnetwork
• Paths
• Nondeterminism
• Recursion
• Top-Down Processing
• Depth-First Processing
• Cat Operation
• Push Operation
• Categorial Grammars
• Rewriting Rules as Functions
• Categories as Functions
• Syntactic Types
• Syntactic Analysis
• Semantic Analysis
• Incremental Analysis
• References

Linguistics 484

Notes Index

Top of Page