Brainscape's Knowledge GenomeTM

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


See full index

Discrete Math 2 > Unit 6 > Flashcards

Unit 6 Flashcards

1
Q

Blank is any type of calculation that includes both arithmetical and non-arithmetical steps and follows steps that provide a solution to a problem.

A

Computation

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

Blank are abstract models that allow computer scientists to reason about what can and cannot be computed by a particular kind of device.

A

Computational models

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

Many blank exist in the field of computer science, including pushdown automata, linear-bounded automata, and Turing machines.

A

computational models

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

If the computational model outputs “yes” in response to a particular input string, then the model blanks the string.

A

accepts

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

If the model outputs “no” in response to a particular input string, then the model blanks the string.

A

rejects

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

The blank accepted by a computational model is the set of all strings which the computational model accepts.

A

language

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

A blank is a set of rules for generating strings.

A

grammar

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

The blank is the set of all strings that can be generated according to the rules of the grammar.

A

language generated by a grammar

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

A blank (plural: finite state automata) consists of a finite set of states with transitions between the states triggered by different input actions.

A

finite state automaton

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

A finite state automaton is also known as a blank.

A

finite state machine (FSM)

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

Blank is the process of solving problems using a physical device. The physical device that can perform computations is referred to as a “computer.”

A

Computation

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

Blank are abstract models that allow computer scientists to reason out what can and what cannot be computed.

A

Computational models

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

Blank receive a string as an input and produce an output based on the input. Some models output “yes” when the input string is accepted by the machine or “no” if it is rejected.

A

Computational models

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

The set of strings accepted by a machine is called a blank. A blank is generated by a set of rules called grammar. The concepts of languages, grammars, and automata are intrinsically connected. A grammar generates a language that is accepted by an automaton.

A

language

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

Blank is a computational model that consists of a finite set of states with transitions between the states triggered by different input actions. It is also called a finite state machine (FSM).

A

Finite state automaton

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

A blank is a finite state automaton whose next state is uniquely determined by the current state and the next input symbol.

A

deterministic finite automaton (DFA)

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

A finite number of blank that the automaton enters during the processing of a string.

A

states

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

The blank, or a finite set of possible input symbols in a string.

A

alphabet

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

A blank, which is a set of rules that determine the next state entered by the automaton based on the current state and the next input symbol received.

A

transition function

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

A blank at which the processing of a string begins.

A

start state

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

One or more blank that represent the acceptance of a string if the automaton ends up in one of those states at the end of processing the string. A string is rejected if the automaton ends up in a non-accepting state at the end of processing the string.

A

accepting states

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

The finite set of states

A

Q

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

The aphabet

A

E

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

The transition function

A

Theta

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

THe state in Q that is the start state

A

q0

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

A state of accepting states that is the saubset of Q

A

F

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

A blank is a finite state automaton whose next state is uniquely determined by the current state and the next input symbol.

A

deterministic finite automaton (DFA)

28
Q

A deterministic finite automaton is a quintuplet (5-tuple) that consists of:

A

a set of states,
a set of symbols (alphabet),
a transition function (set of rules for transitioning between states),
an initial state, and
a set of final, accepting states.

29
Q

Initially the DFA is in the given blank. It initiates its transitions by looking at the first symbol of the input string. The state the DFA will transition to depends on the symbol currently at the beginning of the input string and the blank.

A

initial state
transition function

30
Q

A string is accepted by a DFA if the machine does not have any symbols from the initial string to read and it has transitioned into an blank.

A

accepting state

31
Q

A blank is a directed graph whose nodes represent states.

A

state diagram

32
Q

A state diagram is a visual representation of a blank

A

deterministic finite automation.

33
Q

In a state diagram, blank denote the states of the automation

A

Circles

34
Q

In a state diagram, blank explain the transitions between states, i.e. they model the transition function.

A

The labeled arrows

35
Q

The automaton blank between states jumping from one state to another following the arrow that is labeled by the next alphabet symbol from the input string.

A

transitions

36
Q

In a blank, the rows represent the current state and the columns represent the possible input symbols. Each entry of the table indicates the next state for each current state and input symbol combination.

A

state transition table

37
Q

The blank of a deterministic automation can be represented by a table that defines the state to which the automation transitions, based on the current state. The current states are represented as rows and the current alphabet symbols are represented in the columns of the state transition table.

A

transition function

38
Q

Blank can be described using words, state transition diagrams, or state transition tables, among other methods.

A

DFA transition functions

39
Q

The blank always starts in the “start” state and initiates the transition based on the first symbol of the input string. In the new state it reacts to the second symbol, transitions to a new state, and so on.

A

DFA

40
Q

Some DFAs can build blank as they transition based on the input symbol.

A

output

41
Q

The input and output blank may coincide, but they do not need to. The DFA with output is virtually a rewriting system, one that uses one string and generates another based on the rewriting rules defined by the transition function.

A

alphabets

42
Q

A deterministic finite automaton with output, or blank, produces a response that depends on the current state as well as the most recently received input.

A

DFA with output

43
Q

An input string is accepted if the DFA ends up in an blank after each character in the string is processed. The set of all accepting states is a designated subset of the states.

A

accepting state

44
Q

The property of whether a number is odd or even is called the blank of a number.

A

parity

45
Q

The blank of a DFA is denoted by a doubled circle in the state transition diagram.

A

finite states

46
Q

An input string is blank if the input string resulted in a DFA that is in a finite state.

A

accepted

47
Q

There are languages a DFA cannot recognize, as its blank is limited on the current state and the next symbol of the input string.

A

memory

48
Q

A blank is a finite state automaton whose next state is not uniquely determined by the current state and the next input symbol.

A

non-deterministic finite automaton (NFA)

49
Q

In contrast to a DFA, in which the current state and the next input symbol uniquely determine the next state, an NFA can have more than blank to which the NFA can transition given the current state and the next input symbol.

A

than one possible state (or no state at all)

50
Q

In addition, an NFA can have transitions from one state to another without reading in an input symbol at all, a transition known as an blank and represented by the symbol E.

A

epsilon transition

51
Q

Similar to a DFA, an NFA contains several components.

A

A finite number of states that the automaton enters during the processing of a string.
The alphabet.
The transition function. In an NFA, an input symbol, or no input, can cause a transition to the next state. Because the next state of an NFA can be no state, one unique state, or one of many possible states, the output of the transition function is an element of P(Q), the power set of Q , or the set of all subsets of Q.
The start state.
One or more accepting states.

52
Q

an NFA is also defined using a
blank.

A

5-tuple

53
Q

Blank are a quintuplet, where the transition function maps into the power state of the set of states. The components of the NFAs are the states set, the alphabet, set of final states, initial state, and a transition function.

A

Nondeterministic finite automata

54
Q

NFAs can transition into multiple states with blank or blank

A

one symbol or no symbols.

55
Q

An blank is a transition from one state or another without reading an input symbol.

A

epsilon transition

56
Q

The blank of an NFA can be represented using a state transition diagram.

A

transition function

57
Q

Unlike the DFA there are transitions that do not use a symbol from the input string. The transitions are labeled with the blank and are called epsilon transitions.

A

epsilon symbol

58
Q

The transition function of a blank can be represented by a table that defines the state to which the automation transitions, based on the current state (represented as rows) and the current symbol (represented in the columns of the state transition table), including the epsilon symbol which denotes transitioning without using a symbol from the input.

A

nondeterministic finite automation (NFA)

59
Q

NFAs’ transition functions can be described using blank, blank or blank among other methods.

A

words, state transition diagrams, or state transition tables,

60
Q

Unlike DFAs, NFAs can end up in different blanks

A

states.

61
Q

When determining the transitions of a nondeterministic finite automaton, blank the possible sequences of actions given in an input string must be considered.

A

all

62
Q

Starting with the initial state, follow the blank to arrive to all possible states of an NFA after computation.

A

computations of the NFA

63
Q

An NFA may have blank sequence of transitions for a given input string.

A

more than one valid

64
Q

Some sequences of transitions may lead to a blank. Other sequences may lead to a non- accepting state at the input string.

A

dead end

65
Q

An NFA accepts a string as long as at least one valid sequence of transitions corresponding to the input symbols exists, putting the NFA in an blank at the end of the input string.

A

accepting state

Discrete Math 2 (6 decks)

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