Formal Language and Automata Theory notes f (1).pdf

Question 1

What is automata theory?

Answer 1

The basis for the theory of formal languages.

Question 2

Define a symbol in the context of automata theory.

Answer 2

A character, an abstraction that is meaningless by itself.

Question 3

What is an alphabet?

Answer 3

A finite set of symbols.

Question 4

What is a word in automata theory?

Answer 4

A finite string of symbols from a given alphabet.

Question 5

Define a language in automata theory.

Answer 5

A set of words formed from a given alphabet.

Question 6

What operations can be performed on formal languages?

Answer 6

• Union
• Intersection

Question 7

What are the three ways formal languages are defined?

Answer 7

• Regular expressions
• Standard automata
• Formal grammar system

Question 8

What is the most general and powerful automaton?

Answer 8

The Turing machine.

Question 9

List the four major families of automata.

Answer 9

• Finite-state machine
• Pushdown automata
• Linear-bounded automata
• Turing machine

Question 10

What defines a finite-state machine (FSM)?

Answer 10

An automaton in which the state set Q contains only a finite number of elements.

Question 11

Who were the first to present a description of finite automata?

Answer 11

Warren McCulloch and Walter Pitts in 1943.

Question 12

What distinguishes a Mealy machine from a Moore machine?

Answer 12

A Mealy machine determines its outputs through the current state and the input, while a Moore machine’s output is based upon the current state alone.

Question 13

Define the state transition function of a finite-state machine.

Answer 13

A function which maps an ordered sequence of input events into a corresponding sequence or set of output events.

Question 14

What is a trap state in finite-state machines?

Answer 14

A state where no further input affects the outcome.

Question 15

What is the formal definition of a finite automaton?

Answer 15

A 5-tuple (Q, Σ, δ, q0, F) where Q is the set of states, Σ is the input alphabet, δ is the transition function, q0 is the initial state, and F is the set of accepting states.

Question 16

What does DFA stand for?

Answer 16

Deterministic Finite Automata.

Question 17

What is the characteristic of a deterministic finite automaton (DFA)?

Answer 17

There is only one path for specific input from the current state to the next state.

Question 18

True or False: DFA can accept the null move.

Answer 18

False.

Question 19

What is the graphical representation of a DFA called?

Answer 19

State diagram.

Question 20

What does the initial state of a DFA represent in a state diagram?

Answer 20

Marked with an arrow.

Question 21

How can you describe the transition function of a DFA?

Answer 21

δ: Q x Σ → Q.

Question 22

What is the significance of accepting states in finite automata?

Answer 22

If the input string ends in an accepting state, the input is considered accepted.

Question 23

Fill in the blank: A finite automaton accepts or rejects an input based on a defined set of strings known as the _______.

Answer 23

[language of the automaton]

Question 24

What is an example of a finite automaton application?

Answer 24

Airplane safety control.

Question 25

What is the mathematical representation of a finite automaton?

Answer 25

Q, Σ, δ, q0, F.

Question 26

What is the initial state of a DFA when given input 0?

Answer 26

The DFA changes state to q1.

Question 27

What type of strings can a DFA accept?

Answer 27

Any string which ends with 0.

Question 28

What type of strings will a DFA reject?

Answer 28

Any string which ends with 1.

Question 29

What is the 5-tuple representation of an NDFA?

Answer 29

(Q, ∑, δ, q0, F)

Question 30

What does Q represent in the NDFA definition?

Answer 30

A finite set of states.

Question 31

What does ∑ represent in the NDFA definition?

Answer 31

A finite set of symbols called the alphabets.

Question 32

What is the transition function δ in an NDFA?

Answer 32

δ: Q × ∑ → 2Q.

Question 33

What does q0 signify in the NDFA definition?

Answer 33

The initial state from where any input is processed.

Question 34

What does F represent in the NDFA definition?

Answer 34

A set of final state/states of Q.

Question 35

How is an NDFA graphically represented?

Answer 35

By digraphs called state diagrams.

Question 36

What do the vertices represent in an NDFA state diagram?

Answer 36

The states.

Question 37

How are transitions indicated in an NDFA state diagram?

Answer 37

By arcs labeled with an input alphabet.

Question 38

What indicates the initial state in an NDFA diagram?

Answer 38

An empty single incoming arc.

Question 39

What indicates the final state in an NDFA diagram?

Answer 39

Double circles.

Question 40

What is a key difference between DFA and NDFA regarding transitions?

Answer 40

DFA transitions to a single state; NDFA can transition to multiple states.

Question 41

Can empty string transitions be seen in DFA?

Answer 41

No, they are not permitted.

Question 42

What is the condition for a string to be accepted by a DFA or NDFA?

Answer 42

It ends in an accepting state after reading the string wholly.

Question 43

What is the language L accepted by DFA/NDFA?

Answer 43

{S | S ∈ ∑* and δ*(q0, S) ∈ F}

Question 44

What does L' represent in relation to DFA/NDFA?

Answer 44

The complement of accepted language L.

Question 45

What strings does the DFA accept based on the example provided?

Answer 45

{0, 00, 11, 010, 101, ...}

Question 46

What strings does the DFA reject based on the example provided?

Answer 46

{1, 011, 111, ...}

Question 47

What is one of the examples of a DFA design?

Answer 47

Accept strings that start with 1 and end with 0.

Question 48

What is the regular expression for the set of strings that end in 3 consecutive 1's?

Answer 48

(0 | 1)* 111

Question 49

What is the union operator in regular expressions?

Answer 49

R1 | R2 or R1 U R2.

Question 50

What does the concatenation operator do in regular expressions?

Answer 50

R1R2 combines patterns from R1 and R2.

Question 51

What does the Kleene closure operator represent?

Answer 51

R1* includes epsilon, L(R1), and all concatenations of R1.

Question 52

What is the language of the regular expression (0 + 10*)?

Answer 52

{0, 1, 10, 100, 1000, ...}

Question 53

What does the regular expression (a+b)* represent?

Answer 53

Set of strings of a's and b's of any length including the null string.

Question 54

What does the regular expression (11)* represent?

Answer 54

Set consisting of even number of 1's including empty string.

Question 55

What is the property that states the union of two regular sets is regular?

Answer 55

Property 1.

Question 56

What is an example of a regular expression that denotes an empty language?

Answer 56

φ

Question 57

What does ε represent in regular expressions?

Answer 57

The language containing an empty string.

Question 58

What is the language represented by the regular expression (aa)*(bb)*b?

Answer 58

Strings consisting of even number of a's followed by odd number of b's.

Question 59

What is the set L1 in the context of regular expressions?

Answer 59

{ a, aa, aaa, aaaa, ....} (Strings of all possible lengths excluding Null)

Question 60

What is the set L2 in the context of regular expressions?

Answer 60

{ ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)

Question 61

What is the result of the intersection L1 ∩ L2?

Answer 61

{ aa, aaaa, aaaaaa,.......} (Strings of even length excluding Null)

Question 62

What is the regular expression for the intersection of L1 and L2?

Answer 62

RE (L1 ∩ L2) = aa(aa)*

Question 63

What is the complement of a regular set?

Answer 63

All strings that are not in the set

Question 64

What is the regular expression for the complement of the set L?

Answer 64

RE (L’) = a(aa)*

Question 65

What does the difference of two regular sets represent?

Answer 65

Strings in the first set that are not in the second set

Question 66

What is the regular expression for the difference L1 – L2?

Answer 66

RE (L1 – L2) = a (aa)*

Question 67

What is the property of the reversal of a regular set?

Answer 67

The reversal of a regular set is also regular

Question 68

What is the regular expression for the reversal LR of the set L?

Answer 68

RE (LR) = 01 + 10 + 11 + 10

Question 69

What is the closure of a regular set?

Answer 69

The set formed by concatenating the regular set with itself zero or more times

Question 70

What is the regular expression for the closure of the set L?

Answer 70

RE (L*) = a (a)*

Question 71

What is a pushdown automaton (PDA)?

Answer 71

A mathematical model that extends finite automata with a stack for memory

Question 72

What are the seven tuples that define a PDA?

Answer 72

M = (Q, ∑, Γ, δ, q0 , z0, F)

Question 73

What does 'Q' represent in the context of a PDA?

Answer 73

A finite set of states

Question 74

What does '∑' represent in the context of a PDA?

Answer 74

A finite set of input alphabet/symbols

Question 75

What does 'Γ' represent in the context of a PDA?

Answer 75

A finite stack alphabet

Question 76

What is the transition function 'δ' in a PDA?

Answer 76

It governs the behavior of the automaton, mapping state/input/stack symbol to new state/stack operation

Question 77

What is the initial state 'q0' in a PDA?

Answer 77

The state before making any transitions

Question 78

What does 'z0' represent in a PDA?

Answer 78

The stack start symbol

Question 79

What is meant by the term 'Instantaneous Description' in a PDA?

Answer 79

A triplet (q, w, s) representing the state, unconsumed input, and stack contents

Question 80

What does the turnstile notation represent in PDA transitions?

Answer 80

It connects pairs of IDs representing transitions

Question 81

What is one application of finite automata?

Answer 81

Recognizing patterns in text or data

Question 82

How are finite automata used in programming languages?

Answer 82

To implement regular expressions

Question 83

What is one application of pushdown automata?

Answer 83

Parsing context-free grammars

Question 84

What do pushdown automata model in natural language processing?

Answer 84

They recognize and parse sentences

Question 85

True or False: A pushdown automaton can read an input symbol in every transition.

Answer 85

False

Question 86

Fill in the blank: A PDA has a stack with _______ size.

Answer 86

infinite