Introduction and finite automata

Question 1

LAG

Answer 1

Language, Automata, Grammar

Question 2

Symbol

Answer 2

{ a,b,c,d,0,1,2,3,…}

Question 3

Finite set of symbols

Answer 3

Alphabet

Question 4

Collection of alphabet, Sequence

Answer 4

String {a, aa, aaa, aaaa, …}

Question 5

Collection of Strings

Answer 5

Language L(M), i.e. Strings starting with ‘a’

Question 6

Empty String

Answer 6

∑(a, b) = ∑⁰ = ε

Question 7

Types of Language

Answer 7

Finite, Infinite

Question 8

Automata

Answer 8

Model, Machine to check whether given string is accepted in language or not.

Question 9

Example of Finite Language?

Answer 9

strings of length 4

Question 10

Example of Infinite Language?

Answer 10

strings starts with ‘a’

Question 11

Set of all strings with Length = 0

∑ = (a, b)

Answer 11

∑0, ε, λ

Question 12

Set of all strings with length = 1

∑ = (a, b)

Answer 12

∑1 = {a, b}

Question 13

Kleene Closure

Answer 13

∑#, (a+b)# , {ε, a, b, ab, aab, aba, baa, ….}

All possible strings over ∑= (a, b), here # = *

Question 14

Positive Closure

Answer 14

∑+ , (a + b)+, {a, b, ab, aab, aba, …}

Question 15

(∑+) + (∑0) = ?

Answer 15

∑*

Question 16

What is Grammar?

Answer 16

G = {V, T, P, S}
V = variable
T = Terminal
P = Production Rule
S = Start

Question 17

Example of Grammar?

Answer 17

S -> aSb | ε

a^mb^m, m >=0

Question 18

give examples of “S -> aSb | ε”

Answer 18

{ε, ab, aabb, aaabbb, …}

Question 19

S -> SS
S -> aSb
S-> bSa
S -> ε

Answer 19

n(a) = n(b)

Question 20

Expressing power of any machine can be defined as…

Answer 20

the maximum number of languages it can accept..
if machine M1 can accept more languages then M2 then we can say that expressing power of M1 is greater then M2

Question 21

Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA) have different POWER
T or F ?

Answer 21

FALSE
Languages accepted by NFA,will also be accepted by DFA because we can make DFA corresponding to NFA. So their expressing power is same.

Question 22

Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA) have different POWER
T or F ?

Answer 22

TRUE
In this case languages accepted by NPDA is more then DPDA, so expressing power of NPDA is more then DPDA

Question 23

FA

Deterministic single tape Turing machine and Non-deterministic single tape Turing machine have same POWER
T or F ?

Answer 23

TRUE
Both deterministic and non deterministic turing can accept same language.so there expressing power is same.

Question 24

Single tape Turing machine and multi-tape Turing machine same POWER
T or F ?

Answer 24

FALSE
In turing machine if we increase the number of tape then also language accepted by that machine is same as single tape turing machine.so there expressing power is same.

Question 25

C language is a regular language.
T or F?

Answer 25

FALSE.
The C language is a context sensitive language.
All modern programming languages use CSL.