Brainscape's Knowledge GenomeTM

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


See full index

3 TSY 23-24 > AutomataSA2 - Sheet1 (1) > Flashcards

AutomataSA2 - Sheet1 (1) Flashcards

1
Q

______ is a set accepted by a finite automaton.

A

Regular set (language)

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

A set is closed under an operation if, wherever the operation is applied to members of the set, the result is also a member of the set

A

Closure

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

{ x | x ∊ A or x ∊ B}

A

Union

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

{xy | x ∊ A and y ∊ B}

A

Concatenation

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

{x1x2…xk | k >= 0 and each x1 ∊ A}

A

Star

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

The class of regular languages is c_________

A

closed under Union

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

The Operators of RE

A

The union of two languages L1 and L2 denoted L1 ∪ L2.
The concatenation of two languages L1 and L2, denoted L1L2.
The Kleene Closure or star of a language L denoted by L*
The Positive Closure of a language L denoted by L+

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

The set of those strings that can be formed by taking any number of strings from L, possibly with repetitions and concatenating all of them, including the null string

A

The Kleene Closure or star of a language L denoted by L*

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

The set of those strings that can be formed by taking any number of strings from L, possibly with repetitions and concatenating all of them, excluding the null string

A

The Positive Closure of a language L denoted by L+

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

several operations defines on languages:

A

L1 ∪ L2
L1 ∩ L2
L1L2
-L2
L1*
L1 - L2
L1^R

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

Union, Concatenation, Negation, Kleene Star, Reverse

The general approach is as follows:

A

Build automata (DFA or NFA) for each of the languages involved
Show how to combine the automata in order to form a new automaton which recognizes the desired language
Since the language is represented by NFA/DFA, shall conclude that the language is regular

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

If L1 and L2 are _____, then so is L1 U L2

A

regular languages

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

Create a new start state
Make a ε-transition from the new start state to each of the original start states

A

Union of L1 and L2

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

Put a ε-transition from each final state of L1 to the initial state of L2
Make the original final states of L1 nonfinal

A

Concatenation of L1 and L2

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

Start with a complete Dfa, not with an NFA
Make every final state nonfinal and every nonfinal state final.

A

Negation of L1

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

Make a new start state; connect it to the original start state with a λ-transition
Make a new final state; connect the original final state (which become nonfinal) to it with λ-transitions
Connect the new start state and new final state with a pair of λ-transition

A

Kleen Star of L1

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

Start with an automaton with just one final state
Make the initial state final and final state initial
Reverse the direction of every arc

A

Reverse of L1

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

The same construction is used for both intersection and set difference. The distinction is in how the final states are selected

A

Reverse of L1

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

If L and M are regular languages, then so is L ∩ M

A

Intersection

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

Let A and B be DFA’s whose language are L and M, respectively

Construct C, the product automaton of A and B

Make the final states of C be the pairs consisting of final states of both A and B

Make a state (A, B) as final if both

i) A is a final state in L1 and
ii) B is a final state in L2
A

Intersection

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

Finite automata are like computers in that they receive input and process the input by changing states.

A

Automaton with Output

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

_______ are like computers in that they receive input and process the input by changing states.

A

Finite automata

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

Two models of finite automata that produce more output than a yes/no.

A

Moore Machine
Mealy Machine

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

______ are finite state machines with output value and its output depends only on present state.

A

Moore Machines

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

This machine might be considered as a “counting” machine

A

Moore Machines

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

It can be defined as a six-tuple
M = (Q, q0, Σ, O, ઠ, λ)

A

Moore Machine
Mealy Machine

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

Basically a _____ is just a FA with two extras.

A

Moore machine

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

It has TWO alphabets, an input and output alphabet
It has an output symbol associated with each state. The Machine writes the appropriate output symbol as it enters each state

A

Moore machine

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

The length of output for a ____ is greater than input by 1

A

Moore machine

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

________ are also finite state machines with output value and its output depends only on present state and current input symbol.

A

Mealy Machines

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

This machine might be considered as an “output” producer

A

Mealy Machines

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

_______ are exactly as powerful as ______ (can implement any _____ using a _____, and vice versa)

A

Mealy, Moore, Mealy, Moore

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

_______ move the output function from the state to the transition.

A

Mealy machines

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

_______ move the output function from the state to the transition.
This turns out to be easier to deal with in practice, making Mealy machines more practical

A

Mealy machines

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

There are no accept states in a _____ because it is not a language recogniser, it is an output producer

A

Mealy machine

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

The length of output for a _____ is equal to the length of the input

A

Mealy machine

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

Output depends both upon the present state and the present input

A

Mealy machine

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

Output depends only upon the present state

A

Moore Machine

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

Generally, it has fewer states that Moore Machine

A

Mealy Machine

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

Generally, it has more states than Mealy Machine

A

Moore Machine

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

The value of the output of the transitions and the changes, when the input logic on the present state is done

A

Mealy Machine

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

The value of the output function is a function of the current state and the changes at the clock edges, whenever state changes occur

A

Moore Machine

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

Mealy machines react faster to inputs. They generally react in the same clock cycle

A

Mealy Machine

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

In Moore machines, more logic is required to decode the outputs resulting in more circuit delays. They generally react one clock cycle later

A

Moore Machine

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

Take a blank Mealy Machine transition table format using all states of the given Moore machine
Copy all the Moore Machine transition states into this table format
Check the present states and their corresponding outputs in the Moore Machine state table; if for a state Qi output is m, copy it into the output columns of the Mealy Machine state table wherever Qi appears in the next state

A

Moore to Mealy

46
Q

First find out those states which have more than 1 outputs associated with them
Create two states for these states
Create an empty Moore machine with the new generated state. Output will be associated to each state irrespective of inputs
Fill in the entries of next state using Mealy transition table

A

Mealy to Moore

47
Q

gave a Mathematical model of Grammar which is effective for writing computer languages

A

Noam Chomsky

48
Q

The four types of Grammar according to Noam Chomsky are:

A

TYPE-0
TYPE-1
TYPE-2
TYPE-3

49
Q

Unrestricted Grammar
Recursively Enumerable Language
Turing Machine

A

TYPE-0

50
Q

Context Sensitive Grammar
Context Sensitive Language
Linear Bounded Automaton

A

TYPE-1

51
Q

Context Free Grammar
Context Free Language
Pushdown Automaton

A

TYPE-2

52
Q

Regular Grammar
Regular Language
Finite State Automaton

A

TYPE-3

53
Q

Describe context-free languages (also known as BNF or Backus-Naur Form)

A

Context Free Grammar (CFG)

54
Q

Describe context-free languages (also known as _______)

A

BNF or Backus-Naur Form

55
Q

Describe ______ (also known as BNF or Backus-Naur Form)

A

context-free languages

56
Q

A regular set is an example of ______

A

Context-Free Languages

57
Q

A grammar ‘G’ can be formally described using 4 tuples: ______

A

G = (V, T, S, P)

58
Q

set of variables or non-terminal symbols, generally represented by capital letters (A, B, C, …)

A

V

59
Q

Set of terminal symbols, generally represented by small letters (a, b, c, …)

A

T

60
Q

Start symbol

A

S

61
Q

Production rules for terminals and non-terminals (How to form the string)

A

P

62
Q

A ______ has the form α -> β where α and β are strings on V U T and at least one symbol of α belongs to V.

A

production rule

63
Q

Production rules are used to derive strings

A

Derivation of Strings

64
Q

____ are used to derive strings

A

Production rules

65
Q

The generation of language using a specific rule is called _____

A

derivation

66
Q

In each step, the leftmost variable in sentential form is replaced

A

Leftmost Derivation

67
Q

In each step, the rightmost variable in sentential form is replaced

A

Rightmost Derivation

68
Q

Regular grammar can be divided into two types

A

Right Linear Grammar
Left Linear Grammar

69
Q

A grammar is said to be Right Linear if all productions are of the form:

	A -> xB
	A -> x
A

Right Linear Grammar

70
Q

A grammar is said to be Left Linear if all productions are of the form:

A -> Bx
A -> x

A

Left Linear Grammar

71
Q

____ of each rule is a single variable (non-terminal)

A

LHS

72
Q

_____ of each rule is a string of zero or more variables and terminals

A

RHS

73
Q

________ is an ordered rooted tree that graphically represents the semantic information of strings derived from a Context Free Grammar.

A

A Derivation Tree or Parse Tree

74
Q

Must be labelled by the start symbol

A

Root Vertex

75
Q

Labelled by non-terminal symbols

A

Vertex

76
Q

Labelled by terminal symbols or λ

A

Leaves

77
Q

______ is the final string obtained by concatenating the labels of the leaves of the tree from left to right, ignoring the Nulls.
However, if all the leaves are Null, derivation is Null

A

The derivation or the yield of a parse tree

78
Q

Approaches to draw a derivation tree

A

Top-down Approach
Bottom-up Approach

79
Q

Starts with the starting symbol S.
Goes down to tree leaves using productions

A

Top-down Approach

80
Q

Starts from tree leaves
Proceeds upwards to the root which is the starting symbol S

A

Bottom-up Approach

81
Q

The general idea is to “reduce” the input string back to the start symbol. At each reduction step, replace the RHS of production by LHS non-terminal

A

Bottom-up Approach

82
Q

If a partial derivation tree contains the root S, it is called a _______

A

sentential form

83
Q

Types of Derivation Trees

A

Left Derivation Tree
Right Derivation Tree

84
Q

A Left Derivation Tree is obtained by applying production to the leftmost variable in each step

A

Left Derivation Tree

85
Q

A Right Derivation Tree is obtained by applying production to the rightmost variable in each step

A

Right Derivation Tree

86
Q

In a context-free grammar G, if there is a production in the form: X -> Xa, where X is a non-terminal and ‘a’ is a string of terminals, it is called a _________

A

left recursive production.

87
Q

The grammar having a left recursive production is called a ________

A

left recursive grammar

88
Q

In a context-free grammar G, if there is a production is in the form: X -> aX, where X is a non-terminal and ‘a’ is a string of terminals, it is called a _______

A

right recursive production

89
Q

The grammar having a right recursive production is called a ______

A

right recursive grammar

90
Q

(There exist multiple right-most or left-most derivations for some string generated from that grammar).

A

Ambiguous Grammar

91
Q

A grammar G is said to be ambiguous if there exists two or more derivation tree for some string w ∈ L(G).

A

Ambiguous Grammar

92
Q

In formal language theory, a _______ is a language generated by some ______

A

Context Free Language, Context Free Grammar

93
Q

_______ is identical to the set of languages accepted by Pushdown Automata

A

The set of all CFL

94
Q

______ generalize the class of regular languages, i.e., every regular language is a context-free language

A

The class of context-free languages

95
Q

Every context-free language is not ______

A

necessarily regular.

96
Q

Context-free languages are closed under:

A

Union
Concatenation
Kleene Star operation

97
Q

Let L1 and L2 be two context free languages
Then L1 U L2 is also context free

A

Union
Concatenation
Kleene Star operation

98
Q

L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their union says either of two conditions to be true. So it is also context free language. So ______

A

CFL are closed under union

99
Q

Let L1 and L2 be two context free languages
Then L1L2 is also context free

A

Concatenation

100
Q

Let L be a context free languages
Then L* is also context free

A

Kleene Star

101
Q

Context-free languages are not closed under:

A

Intersection
Intersection with Regular Language
Complement

102
Q

If L1 and L2 are context free languages, then L1 ⋂ L2 is not necessarily context free

A

Intersection

103
Q

if L1 is a regular language and L2 is a context free language, then L1 ⋂ L2 is a context free language.

A

Intersection with Regular Language

104
Q

if L1 is a context free language, then L1’ may not be context free

A

Complement

105
Q

Which of the following is a correct statement?

None of the mentioned

Moore machine has no accepting states

Mealy machine has accepting states

All of the mentioned

We can convert Mealy to Moore but not vice versa

A

None of the mentioned

106
Q

The ratio of number of inputs to the number of output in a mealy machine can be given as:
Group of answer choices

1

None of the mentioned

n+1: n

n: n+1

A

None of the mentioned

107
Q

Let L = {0, 1}, the Kleene closure L* is all strings of 0’s and 1’s including the _____ string.
Group of answer choices

1

bit

0

null

A

null

108
Q

The total number of states and transitions required to form a Moore machine that will produce residue mod 3.

None of the above

2 and 5

3 and 5

3 and 6

2 and 4

A

3 and 6

109
Q

In Moore machine, output is produced over the change of:

transitions

states

golden state

None of the mentioned

transition & states

A

states

110
Q

Which one among the following is true?

A mealy machine

Group of answer choices

produces a grammar

has less circuit delays

produces a language

can be converted to NFA

A

has less circuit delays

3 TSY 23-24 (19 decks)

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