Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Adv Topics In Cs > Test 1 > Flashcards

Test 1 Flashcards

1
Q

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

A

alphabet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

The elements of the set are called:

A

symbols

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

string

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

|x|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

the concatenation of two strings

A

XY

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

reversal: the reverse of a string x=ab

A

ba

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

empty string

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Denoted as “zero or more”:

A

Sigma*

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Always infinite

A

Sigma*

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

{Epsilon, 1, 11, 111, …}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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 .

A

Kleene closure

Kleene star

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

regular expression

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Regular

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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:

A

meta-characters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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 ]

A

character classes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

$

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

finite-state automaton (FSA)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

states

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

start state.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

accepting or final

Accepted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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.

A

transition function

22
Q

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:

A

Enigma- transition

23
Q

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.

A

nondeterministic finite-state automaton (NFA)

24
Q

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

A

NFA

DFA

25
Q

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

A

NFA

26
Q

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

A

regular expression

27
Q

The intersection of two regular languages is a regular language:

A

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.

28
Q

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.

A

English and the artificial languages

29
Q

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

A

generative grammar

30
Q

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

A

parse

31
Q

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.”

A

rewriting rule

32
Q

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

A

production rules or productions

33
Q

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.

A

context-free grammar

34
Q

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

A

non-terminal symbols

35
Q

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

A

terminal symbols.

36
Q

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

A

start symbol

37
Q

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

A

context-free language

38
Q

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

A

equivalent

39
Q

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

A

derivation

40
Q

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.

A

balanced parentheses

41
Q

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 .

A

right-regular grammar

42
Q

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

A

Palendrome

43
Q

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:

A

Backus-Naur Form or BNF

44
Q

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

A

syntactic category

45
Q

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:

A

ident

46
Q

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.

A

parsing

47
Q

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:

A

bottom-up parsing

top-down parsing

48
Q

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

A

parse tree

49
Q

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.

A

pushdown automata

50
Q

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

A

stack

51
Q

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 _________

A

top

pushing

popping

52
Q

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:

A

deterministic

Adv Topics In Cs (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions