Cs 4114 Final Exam Terms

Front 1

Alphabet

Back 1

Is a finite set of symbols

Front 2

Ambiguity

Back 2

A grammar is unambiguous if every sentence in the grammar has a unique leftmost derivation. A grammar is ambiguous if it is not unambiguous

Front 3

Inherent Ambiguity

Back 3

A CFL is inherently ambiguous if every CFG that generates L is ambiguous

Front 4

Cardinality

Back 4

Number of elements in a set

If there is a one to one, onto function f: {1,2…n} => X, then X has cardinality n, written card (X)= n X is finiteIf Y is not finite, then there is a one to one function g; Y ->Y that is not onto Y is infinite

Front 5

Cartesian Product

Back 5

A Cartesian product is a mathematical operation which returns a set (or product set or simply product) from multiple sets. That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. Products can be specified using set-builder notation

Front 6

Chomsky Hierarchy (types, acceptors, grammars)

Back 6

Specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky-Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by Noam Chomsky in 1956.It is also named after Marcel-Paul Schützenberger, who played a crucial role in the development of the theory of formal languages.A formal grammar of this type consists of a finite set of production rules (left-hand side → right-hand side), where each side consists of a sequence of the following symbols:a finite set of nonterminal symbols (indicating that some production rule can yet be applied)a finite set of terminal symbols (indicating that no production rule can be applied)a start symbol (a distinguished nonterminal symbol)

Front 7

Chomsky Normal Form (CNF) and CNF algorithms

Back 7

If all of its production rules are of the form:A → BC, orA → a, orS → ε,Where A, B, and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string. Also, neither B nor C may be the start symbol, and the third production rule can only appear if ε is inL(G), namely, the language produced by the context-free grammar G.Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form and has a size no larger than the square of the original grammar's size.

Front 8

Context Free Grammar

Back 8

a set of recursive rewriting rules (or productions) used to generate patterns of strings. A CFG consists of the following components: a set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar.

Front 9

Countable

Back 9

Able to be counted (?)

Front 10

Denumerable or Countably Infinite

Back 10

A set is countably infinite if its elements can be put in one-to-one correspondence with the set of natural numbers. In other words, one can count off all elements in the set in such a way that, even though the counting will take forever, you will get to any particular element in a finite amount of time.

Front 11

Derivation, Derivation Tree

Back 11

For every derivation of sentential form S -> w, there is a corresponding derivation tree (DT) which is an oriented tree with these characteristics

Front 12

DFA Minimization

Back 12

Is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.

Front 13

DFA Constructions (complement, union, intersection)

Back 13

Deterministic finite automata, the drawing with the circles and crap

Front 14

Equivalence of regular sets, grammers, expressions, and DFAs.

Back 14

Kleene's Theorem

We have shown how to convert a regular expression to an NFA; the proof that these represent the same language is straightforward (by induction). However, we have asserted that there is a correspondence in both directions; this is formalised in Kleene's Theorem:

Front 15

Equivalence relations and classes

Back 15

Reflexivity: xRx
Symmetry: If xRy then yRx

Front 16

Expression Graphs

Back 16

`is a directed graph satisfying these propertiesNode are called statesOne node is the start stateSome of the nodes (possibly noe) are final statesEvery arc is labeled with a regular expression

Front 17

Function

Back 17

X-> Y is a relation on X and Y such that if x € X, y1, y2 € Y and (x, y1) (x,y2) € f then y1 = y2

Front 18

Grammar

Back 18

a set of production rules for strings

The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax.

Front 19

Grammar Graphs

Back 19

Start with a CFG G= (V, ∑, P,S)

Front 20

Language

Back 20

Start with an alphabet ∑The set of all strings over ∑ is denoted ∑*A language over ∑ is any subset of ∑*

Front 21

Leftmost, Rightmost Derivations

Back 21

If we always expanded the left/right most variable first

Front 22

NFAs and conversion to DFAs

Back 22

http://fleder44.net/312/notes/26_converting_nfa/index.html

Front 23

Palindrome

Back 23

Reverse of word = word

Front 24

PDAs

Back 24

Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines. Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages. Mainly the former are used in parser design.

Front 25

Production Rule

Back 25

a rewrite rule specifying a symbol substitution that can be recursively performed to generate new symbol sequences.

Front 26

Pumping Lemmas (Regular and Context Free)

Back 26

Describes an essential property of all regular languages. Informally, it says that all sufficiently long words in a regular language may be pumped — that is, have a middle section of the word repeated an arbitrary number of times — to produce a new word that also lies within the same languageis a lemma that gives a property shared by all context-free languages. It generalizes the pumping lemma for regular languages.

Front 27

Recursive Definitions

Back 27

Method used to define a set X

Explains how to generate an element of X

Especially useful if X is infinite

Also called inductive definitions

Front 28

Regular Expressions

Back 28

a special text string for describing a search pattern

Front 29

Regular Sets ( Regular Languages)

Back 29

the languages that are generated by Type-3 grammars (regular grammars).

Front 30

Regular Grammars

Back 30

A -> aB
a -> a

A -> empty

Front 31

Relations

Back 31

???

Front 32

Binary Relations

Back 32

On a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = A × A. More generally, a binary relation between two sets A and B is a subset of A × B. The terms correspondence, dyadic relation and 2-place relation are synonyms for binary relation.

Front 33

Reversal

Back 33

...

Front 34

Sentential Form

Back 34

any string derivable from the start symbol

Front 35

Sets

Back 35

A collection of objects

Front 36

Power set

Back 36

The set of all subsets

Front 37

String

Back 37

A finite sequence of symbols from the alphabet

Front 38

Terminal Vocabulary

Back 38

Terminal symbols are literal symbols which may appear in the outputs of the production rules of a formal grammar and which cannot be changed using the rules of the grammar. Applying the rules recursively to a source string of symbols will usually terminate in a final output string consisting only of terminal symbols.

Front 39

Nonterminal Vocabulary

Back 39

Nonterminal symbols are those symbols which can be replaced. They may also be called simply syntactic variables. A formal grammar includes a start symbol, a designated member of the set of nonterminal from which all the strings in the language may be derived by successive applications of the production rules. In fact, the language defined by a grammar is precisely the set of terminal strings that can be so derived.