week 8,9,10 Finite automata

Question 1

How does finite automaton work

Answer 1

.At regular time intervals:
. reads the first character from the inputted word
. Head moves to the next character
.control device determines ( the next state)
. Stops when the head reaches the last character of the input word ( when it hits the first blank cell)
. If it ends in an accepted state, word is accepted and part of language
. If it doesnt word is not part of language

Question 2

How does the control device determine the next state

Answer 2

. The previous state
. The character read from the tape

Question 3

What does it mean by a DFA ( deterministic)

Answer 3

. For each state ( and symbol ) there is an arrow coming out of the state labelled by the symbol
. Next state is determined by :
( letter/ character read , current state)

. Never gets stuck
. No choice in what route to take

Question 4

Language of a DFA?

Answer 4

set of all words over alphabet that it accepts

Question 5

Properties of an NFA

Answer 5

. There can be choices (on what state to move to)
. control device can get stuck ( there is no arrow leaving the state with the desired symbol)
. There are ε- jumps

Question 6

Difference between transition table of NFA and DFA

Answer 6

. There is an e - coloumn
. cells can be contain 0 , 1 or more than one states

Question 7

A NFA can be regarded as a DFA if …

Answer 7

. cells contain one state only and all cell in ε column are empty

Question 8

Word in NFA accepted iff

Answer 8

There is at least one computation in the input word (as there can be multiple variations in choices taken) that is accepted

. accepted is NOT same as being stuck on a favourable state

Question 9

What is the subset construction

Answer 9

Method to turn NFA to DFA

Question 10

What are the new states in subset construction

Answer 10

named after subsets of original states

Question 11

what is new inital state in subset construction

Answer 11

subset containing the original initial state in NFA and any states reachable by ε jumps from original initial states

Question 12

New faourable state

Answer 12

Those subsets that contain at least one of NFA’s old favourable states

Question 13

What is the general rule from going from a state to the next state in subset construction

Question 14

What usually has more states DFA or NFA

Answer 14

DFA

Question 15

What is the worst case number of no of states in DFA

Answer 15

2^ ( no of states in NFA)

Question 16

What are main symbols in regular expressions

Answer 16

union , asterisk , comma , brackets with comma , ε , empty set

Question 17

what is a regular language

Answer 17

A language that can be expressed via a regular expression