TOC

Question 1

the length every symbol is

Answer 1

1

Question 2

no of suffixes and prefixes of a string is

Answer 2

n+1

Question 3

total no of substring of a string if every symbol is distinct

Answer 3

n(n+1)/2 + 1

Question 4

E^* means

Answer 4

Set of all strings possible by that alphabet

Question 5

What is a language ?

Answer 5

subset of E^*

Question 6

How is phi a language?

Answer 6

generally a language is a subset of E^* and an empty set is a subset of every set hence.

Question 7

L.phi =?

Answer 7

phi according to definition A.B={wx|w€A,x€B}we cant show any string that belongs to phi hence

Question 8

what is the transition function?

Answer 8

its a function mapping QxE->Q

Question 9

the language accepted by dfa is

Answer 9

Regular language

Question 10

no of states in dfa of modulo counting k is

Answer 10

k

Question 11

no of states in dfa of divisibility of language by n
(actual division)

Answer 11

<=n

Question 12

no of states in dfa of the language the kth symbol from the right is

Answer 12

2^k

Question 13

How does converting final <->non final states make a complement of a dfa?

Answer 13

Complement means collection of the strings that end in non final states to accept them just convert final into non final and vice versa

Question 14

What does product automata can guarantee?

Answer 14

The mdfa contains <=product of no of states in each dfa

Question 15

What are distinguishable and non distinguishable states?

Answer 15

&(A,w)<-F <-> &(B,w)<- final and vice versa

Question 16

By what string final and non final strings are always distinguishable?

Answer 16

Epsilon coz final stays in final by epsilon and non final stays in non final by epsilon

Question 17

What does null move means?

Answer 17

Moving from one state to another without reading any symbol

Question 18

Why fo we same symbol for null mobe and null string?

Answer 18

€ab€aaa€

Question 19

What is the transition function of NFA?

Answer 19

Q x (£ u {€}) ->2^k states