Test 1

Question 1

In formal language theory, an __________ is a finite, non-empty set.

Answer 1

alphabet

Question 2

The elements of the set are called:

Answer 2

symbols

Question 3

A finite sequence of symbols a 1 a 2 …a n from an alphabet is called a ________ over that alphabet.

Answer 3

string

Question 4

the length of a string is the number of symbols in it. The notation for the length of is:

Answer 4

|x|

Question 5

the concatenation of two strings

Answer 5

XY

Question 6

reversal: the reverse of a string x=ab

Answer 6

ba

Question 7

Similarly, language theory has a special symbol epsilon which is used to represent the __________, the string with no symbols in it .

Answer 7

empty string

Question 8

Denoted as “zero or more”:

Answer 8

Sigma*

Question 9

Always infinite

Answer 9

Sigma*

Question 10

Is sigma = {1}, then what is sigma*?

Answer 10

{Epsilon, 1, 11, 111, …}

Question 11

If we take the union S^ 0 union S^ 1 union S^ 2 union… then the resulting set is the set of all strings formed by concatenating zero or more strings from S, and is denoted S. The set S is called the ___________ of S, and the operator is called the __________ operator .

Answer 11

Kleene closure

Kleene star

Question 12

One way of describing the grammatical structure of the strings in a language is to use a mathematical formalism called:

Answer 12

regular expression

Question 13

A language is this if it is generated by a regular expression:

Answer 13

Regular

Question 14

of the alphabet and special symbols such a and that are used to construct expressions. These special symbols, which are not part of the language being described but are used in the description, are called:

Answer 14

meta-characters

Question 15

To make it easier to deal with the large number of characters in the alphabet, _____________ are introduced. This consists of a list of characters enclosed between brackets and [ and ]

Answer 15

character classes

Question 16

A meta-character to match the end of the line:

Answer 16

$

Question 17

is a machine which takes as input, a finite string of symbols from some alphabet sigma

Answer 17

finite-state automaton (FSA)

Question 18

There is a finite set of ________ in which the machine can find itself.

Answer 18

states

Question 19

The state it is in before consuming any input is called the:

Answer 19

start state.

Question 20

Some of the states are _________ or _________ . If the machine ends in such a state after completely consuming an input string, the string is said to be ____________ by the machine

Answer 20

accepting or final

Accepted

Question 21

The actual functioning of the machine is described by something called a ________________, which specifies what happens if the machine is in a particular state and looking at a particular input symbol.

Answer 21

transition function

Question 22

The start state of the compiler when parsing a function declaration might be “expecting a return type” then with no input consumed, the compiler can move to the state “ expecting a legal function name “. To model this, it might seem reasonable to allow transitions that do not require the consumption of input. such transitions are called:

Answer 22

Enigma- transition

Question 23

is the same as a deterministic finite-state automaton except that the transition function is no longer a function that maps a state-input pair to a state; rather, it maps a state-input pair or a state-pair to a set of states.

Answer 23

nondeterministic finite-state automaton (NFA)

Question 24

Every languages that is accepted by an ______ is accepted by a _____

Answer 24

NFA

DFA

Question 25

Every language generated by a regular expression can be recognized by an:

Answer 25

NFA

Question 26

Every language that is accepted by a DFA or an NFA is generated by a:

Answer 26

regular expression

Question 27

The intersection of two regular languages is a regular language:

Answer 27

The union of two regular languages is a regular language The concatenation of two regular languages is a regular language The complement of a regular language is a regular language. The Kleene closure of a regular language is a regular language.

Question 28

BOTH NATURAL LANGUAGES , such as __________________________ used for programming have a structure known as grammar or syntax. order to form legal sentences or programs , the parts of the language must be fit together according to certain rules. For natural languages , the rules are somewhat informal. For programming languages, the rules are absolute, and programs that violate the rules will be rejected by a compiler.

Answer 28

English and the artificial languages

Question 29

is a set of rules that can be used to generate all the legal strings in a language.

Answer 29

generative grammar

Question 30

a string means to determine how that string can be generated according to the rules.

Answer 30

parse

Question 31

specifies that a certain string of symbols can be substituted for all or part of another string. If w and u are strings, then is w->u is this rule that specifies that the string can be replaced by the string u. The symbol is read "can be rewritten as."

Answer 31

rewriting rule

Question 32

Rewriting rules are also called ____________________, and can also be read as "produces”.

Answer 32

production rules or productions

Question 33

every rewriting rule has the form A -> w, where A is single symbol and w is a string of zero or more symbols. This grammar is "context-free" in the sense that can be substituted for A wherever A occurs in a string, regardless of the surrounding context in which A occurs.

Answer 33

context-free grammar

Question 34

The symbols that occur on the left-hand sides of production rules in a context-free grammar are called:

Answer 34

non-terminal symbols

Question 35

The strings on the right-hand sides of the production rules can include non -terminal symbols as well as other symbols, which are called:

Answer 35

terminal symbols.

Question 36

In every context-free grammar, one of the non-terminal symbols is designated as the __________ of the grammar.

Answer 36

start symbol

Question 37

A language is said to be a ______________ if there is a G such that L(G) is L.

Answer 37

context-free language

Question 38

Two context-free grammars that generate the same language are said to be __________

Answer 38

equivalent

Question 39

This sequence has the form S => x1 => x2 =>… => w. Such a sequence is called a __________ of w.

Answer 39

derivation

Question 40

Closely related to this idea of matching a's and b's is the idea of _______________. Consider a string made up of parentheses , such as (()()()). The parentheses in this sample string are balanced because each left parenthesis has a matching right parenthesis , and the matching pairs are properly nested.

Answer 40

balanced parentheses

Question 41

is a context-free grammar in which the right-hand side of every production rule has one of the following forms: the empty string; a string consisting of a single non-terminal symbol; or a string consisting of a single terminal symbol followed by a single non-terminal symbol .

Answer 41

right-regular grammar

Question 42

A string that reads the same backwards and forwards such as “mom” and “radar”

Answer 42

Palendrome

Question 43

the notation that is used for grammars in the context of programming languages is somewhat different from the notation introduced. The notation that is used is called:

Answer 43

Backus-Naur Form or BNF

Question 44

Note that a BNF non-terminal usually represents a meaningful:

Answer 44

syntactic category

Question 45

I will use the symbol number to represent a numerical token. Similarly, every variable name, subroutine name, or other identifier in the program is represented by the same tokenwhich I will denote as:

Answer 45

ident

Question 46

The goal is to find a derivation of the string, using the production rules of the grammar, or to show that no such derivation exists . This is known as _________ the string.

Answer 46

parsing

Question 47

Because the steps in the derivation are generated from "bottom to top," LR(1) parsing is a type of: LL(1) parsing, on the other hand, generates the steps in a left derivation from "top to bottom" and so is a type of:

Answer 47

bottom-up parsing top-down parsing

Question 48

displays the generation of a string from the start symbol of a grammar as a two dimensional diagram.

Answer 48

parse tree

Question 49

The abstract machines known as ______________ can be used to define context-free languages. That is, a language is context-free if and only if there is a automaton that accepts that language.

Answer 49

pushdown automata

Question 50

A pushdown automaton is essentially a finite automaton with an auxiliary data structure known as a ________. consists of a finite list of symbols

Answer 50

stack

Question 51

The end of the list where items can be added and removed is called the _____ of the stack. Adding a symbol at the top of the stack is referred to as _________ a symbol onto the stack, and removing a symbol is referred to as _________

Answer 51

top pushing popping

Question 52

The computation of a pushdown automaton can involve nondeterminism. That is, at some point in the computation, there might be more than one transition rule that apply. When this is not the case that is, when there is no circumstance in which two different transition rules apply then we say that the pushdown automaton is:

Answer 52

deterministic