Free Printable Theory of Computations -SET 6

1.

1. Finite state machine is represented by -------------- tuples

a)

4

b)

5

c)

6

d)

3

2.

2.The transition function of a DFA is

a)

Q X Σ→2Q

b)

Q X Σ→Q

c)

Q X Σ→2 ⁿ

d)

Q X Σ→2n

3.

3. Basic limitations of finite state machine is cannot remember

a)

large amount of information

b)

state transitions

c)

grammar for a language

d)

language generated

4.

4. A finite automata recognizes

a)

Any Language

b)

Context Sensitive Language

c)

Context Free Language

d)

Regular Language

5.

5. An NFA’s transition function returns

a)

A Boolean value

b)

A state

c)

A set of states

d)

An edge

6.

6. For which of the following applications regular expressions can be used ?

a)

Designing compilers

b)

Developing text editors

c)

Simulating sequential circuits

d)

All of these

7.

7. The transition function of a NFA is

a)

Q X Σ→2^Q

b)

Q X Σ→Q

c)

Q X Σ→2ⁿ

d)

Q X Σ→2n

8.

8. ε-closure of state is combination of self state and

a)

ε-reachable state

b)

initial state

c)

final state

d)

all the above

9.

9.Number of states require to accept string ends with 101

a)

3

b)

4

c)

2

d)

can’t be represented

10.

10. W is any string whose length is n in {0, 1}* then minimum number of states in a NFA that accepts L is

a)

n

b)

2n

c)

n + 1

d)

n - 1

11.

11.Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is

a)

(1 + 010)*

b)

(01 + 10)*

c)

(1 + 010)* (0 + λ)

d)

(1 + 01)* (0 + λ)

12.

12. The behavior of a NFA can be stimulated by DFA

a)

always

b)

sometimes

c)

never

d)

depend on NFA

13.

13.The DFA shown above accepts the set of all strings over {0, 1} that

a)

End with 00

b)

End with 0

c)

Begin either with 0 or 1

d)

Contain the substring 00

14.

Statement 1: FA can be represented graphically;

Statement 2: The nodes can be its states

Statement 3: The edges or arcs can be used for transitions.

Which of the following make the correct combination?

a)

Statement 1 is false but Statement 2 and 3 are correct

b)

Statement 1 and 2 are correct while 3 is wrong

c)

None of the mentioned statements are correct

d)

All of the mentioned

15.

15. ___________ states are called the halt states.

a)

ACCEPT AND START

b)

ACCEPT and READ

c)

ACCEPT AND WRITE

d)

ACCEPT and REJECT

16.

16.L={w | w=0ⁿ1^m for n,m>0| } then L is accepted by which of the following

a)

DFA

b)

NFA

c)

ε-NFA

d)

All the above

17.

a)

I and II

b)

II and III

c)

I,II and III

d)

none of the above

18.

18. e-closure of (q0) is

a)

{q0,q1,q2,q3,q4}

b)

{q0,q1,q3,q4}

c)

{q0,q1,q2,q3}

d)

{q1,q2,q3}

19.

19.which of the following equivalence is true?

a)

∅ * = ε

b)

ε* = ∅

c)

∅ + ε = ε

d)

∅*. ε = ε

20.

20.Which of the following stmts are true:

a)

There exist a DFA which has infinitely many states

b)

There exist a DFA which accepts a language containing infinitely many strings

c)

For every NFA with ‘n’ states, there exist an equivalent DFA with ‘n’ states

d)

None of the above

21.

a)

aba

b)

abaabb

c)

aaba

d)

babab

22.

a)

a

b)

b

c)

c

d)

d

23.

a)

a

b)

b

c)

c

d)

d

24.

a)

q1

b)

q2

c)

q3

d)

q4

25.

a)

a

b)

b

c)

c

d)

d

26.

a)

q0

b)

q1

c)

q2

d)

q3

27.

b

a)

a

b)

q1

c)

c

d)

d

28.

a)

0

b)

1

c)

A

d)

any symbol

29.

a)

q0

b)

q1,q3,q6

c)

q5,q6

d)

q2,q4,q5

30.

a)

yes

b)

no

31.

Obtaining the final string by concatenating the labels of the tree from left to right is called yield of a _____ tree.

a)

Perfect

b)

Concatenation

c)

Leaves crafting

d)

Parse

32.

Given the grammar G = {{S, B}, {0,1}, {S}, P}, what are {0,1}?

a)

Non terminals

b)

Production

c)

Starting Symbol

d)

Terminals

33.

What is an approach in CFG that starts derivation from the tree leaves?

a)

Bottom-down approach

b)

Top-up Approach

c)

Bottom-less Approach

d)

Bottom-up Approach

34.

Which among the two approaches reduces an input string back to the start symbol?

a)

Top down

b)

Bottom up

35.

What is an approach that draws the derivation tree from the start symbol to the tree leaves?

a)

Topping approach

b)

Top gearing approach

c)

Top down approach

d)

Derivation down approach

36.

A (a) form is a tree wherein if the partial derivation tree contains the root vertex.

37.

What is a type of derivation tree that is obtained by applying production to the rightmost variable in each step?

a)

Right part tree

b)

Right derivation tree

c)

Production processing rightly

d)

Rightly derivation tree

38.

A left recursive production has a form of X --> aX. True or False

a)

True

b)

False

39.

A grammar G is said to be ________ if there exists two or more derivation tree for some sting in a L(G).

a)

Ambitions

b)

Ambigious

c)

Ambiguous

d)

Ambitious

40.

The set of all CFL is identical to the set of languages accepted by (a) Automata.

41.

Which of the following is NOT considered closed for Context free languages?

a)

Concatenation

b)

Union

c)

Kleen Star

d)

Complement

42.

During the derivation of a tree, if the leaves are null, then the derivation is null. True or False

a)

True

b)

False

43.

Pushdown automata accepts

a)

Regular language

b)

Context-free language

c)

Context-sensitive language

d)

Both Regular and context-free language

44.

What is addition in pushdown automata as compare to finite state automata?

a)

Stack memory

b)

Input Tape

c)

Read Head

d)

None of them

45.

A pushdown automata behaves like an finite state automata when the number of auxiliary memory it has, is

a)

1

b)

2

c)

0

d)

3

46.

Pushdown automata behaves like Turing machine when it has the number of auxiliary memory

a)

One or more

b)

Two or more

c)

Zero

d)

Can't behave like Turing machine

47.

A PDA machine configuration (p, w, y) can be correctly represented as:

a)

(current state, unprocessed input, stack content)

b)

(unprocessed input, stack content, current state)

c)

(current state, stack content, unprocessed input)

d)

none of the mentioned

48.

A DPDA is a PDA in which:

a)

More than one state can have two or more outgoing transitions

b)

Atleast one state has more than one transitions

c)

No state p has two outgoing transitions

d)

None of the mentioned

49.

State true or false:

Statement: For every CFL, G, there exists a PDA M such that L(G) = L(M) and vice versa.

a)

true

b)

false

50.

How many ways PDA can be accepted?

a)

1

b)

2

c)

3

d)

4

51.

L = { a^n b^n c^m | m, n >=1} is ------------------------------ Language

a)

Regular Language

b)

Context Free language

c)

Recursively Enumerable Language

d)

Context Sensitive Language

52.

PDA is more powerful than

a)

Turing machine

b)

Finite automata

c)

Both (a) and (b)

d)

None of these

53.

PDA can be represented with the help of

a)

Instantaneous description

b)

Transition diagram

c)

Transition table

d)

All of these

54.

The push down automata indicate the acceptance of input string in terms of

a)

Finial state

b)

Empty store

c)

Both (a) and (b)

d)

None of these

55.

Which type of symbols contain in the stack of PDA

a)

Variable

b)

Terminal

c)

Both (a) and (b)

d)

None of these

56.

The symbol Z0 in formal definition of PDA is used for

a)

Stack symbol

b)

Input symbol

c)

Both (a) and (b)

d)

None of these

57.

Which of the following option resembles the given PDA?

a)

{0^n1^n|n>=0}

b)

{0^n1^2n|n>=0}

c)

{0^2n1^n|n>=0}

d)

None of the mentioned

58.

A push down automaton employs ________ data structure.

a)

Queue

b)

Linked List

c)

Hash Table

d)

Stack

59.

State true or false:

Statement: The operations of PDA never work on elements, other than the top.

a)

true

b)

false

c)

may be

d)

Can't say

60.

Push down automata accepts _________ languages.

a)

Type 3

b)

Type 2

c)

Type 1

d)

Type 0

61.

Which among the following is not a part of the Context free grammar tuple?

a)

End symbol

b)

Start symbol

c)

Variable

d)

Production

62.

The moves in the PDA is technically termed as:

a)

Turnstile

b)

Shifter

c)

Router

d)

None of the mentioned

63.

Obtaining the final string by concatenating the labels of the tree from left to right is called yield of a _____ tree.

a)

Perfect

b)

Concatenation

c)

Leaves crafting

d)

Parse

64.

Given the grammar G = {{S, B}, {0,1}, {S}, P}, what are {0,1}?

a)

Non terminals

b)

Production

c)

Starting Symbol

d)

Terminals

65.

What is an approach in CFG that starts derivation from the tree leaves?

a)

Bottom-down approach

b)

Top-up Approach

c)

Bottom-less Approach

d)

Bottom-up Approach

66.

Which among the two approaches reduces an input string back to the start symbol?

a)

Top down

b)

Bottom up

67.

What is an approach that draws the derivation tree from the start symbol to the tree leaves?

a)

Topping approach

b)

Top gearing approach

c)

Top down approach

d)

Derivation down approach

68.

A (a) form is a tree wherein if the partial derivation tree contains the root vertex.

69.

What is a type of derivation tree that is obtained by applying production to the rightmost variable in each step?

a)

Right part tree

b)

Right derivation tree

c)

Production processing rightly

d)

Rightly derivation tree

70.

A left recursive production has a form of X --> aX. True or False

a)

True

b)

False

71.

A grammar G is said to be ________ if there exists two or more derivation tree for some sting in a L(G).

a)

Ambitions

b)

Ambigious

c)

Ambiguous

d)

Ambitious

72.

The set of all CFL is identical to the set of languages accepted by (a) Automata.

73.

Which of the following is NOT considered closed for Context free languages?

a)

Concatenation

b)

Union

c)

Kleen Star

d)

Complement

74.

During the derivation of a tree, if the leaves are null, then the derivation is null. True or False

a)

True

b)

False

75.

Which of the following is not a Context-Free Grammar ?

a)

$a^nb^{4m}$ Where mn $\ge$ 1

b)

$a^ib^j$ Where mn $i\ne2j+1$

c)

$a^{n^n}$ Where n $\ge$ 1

d)

$a^mb^{m+n_{ }}c^n$ Where mn $\ge$ 1

76.

Which of the following RE are equivalent?

1. (00)* 2. (00)* ( $\epsilon$ +o)*

3. 0* 4. 0(00)*

a)

1 and 2

b)

2 and 3

c)

2 and 4

d)

3 and 4

77.

How many states does Minimum DFA needs to construct a language where all string ending with "ab"

a)

2

b)

3

c)

4

d)

5

78.

$D_p$ $N_p$ $D_f$ $N_f$ are PDA, NPDA, DFA and NFA,respectively.

Which of the following statement is correct ?

a)

$D_p$ = $N_p$

b)

$D_f$ = $D_p$

c)

$D_f$ = $N_f$

d)

$N_p$ = $N_f$

79.

RE= (01+11)*

How many states need to design a minimum DFA?

a)

2

b)

3

c)

1

d)

4

80.

Which of the following statement is true ?

a)

Containing aaa

b)

any number of "a" followed by "b"

c)

any number of "b" followed by "a"

d)

Multiple of a where a mod 3 =0

81.

Identify the language generated by the grammar

S-->XY

X-->aX/a

Y-->bY/b

a)

$a^nb^m\ \ where\ mn\ge0$

b)

$b^ma^n\ \ where\ mn\ge0$

c)

$a^nb^m\ \ where\ mn>0$

d)

$a^nb^m\ \ where\ m\ge n$

82.

let L1 and L2 be context free language and regular language, respectively. Then which of the following statement is True

a)

Compliment of L1 is not regular

b)

Compliment of L2 is not regular

c)

Compliment of L2 is regular

d)

L1-L2 is not a context free

83.

L1= S-->aSB/ab

L2= S--> Sab/ab

P:L1 is regular language

Q: L2 is context free language

Which of following statement true?

a)

P true and Q False

b)

Q true and P False

c)

P true and Q True

d)

P False and Q False

84.

L1: { $0^p1^q0^r,\ where\ p=q\ and\ pqr\ge0$ }

L2: $0^p1^q0^r,\ where\ p=q\ =r,\ and\ pqr\ge0$

a)

L1 is context free

b)

L2 is context free

c)

L2 is context free

d)

L1 is not a context free

85.

L is a language accepted by the turning machine. x is a string accepted by TM is a

a)

Decidable problem

b)

Undecidable problem

c)

X can be accepted by CFG

d)

X can be accepted by RG

86.

L1= $a^nb^m\ where\ n=m,\ nm>0\$

L2= $a^nb^m\ where\ nm>0\$

L= L1 U L2 is

a)

L is regular grammar

b)

L is regular but not context free

c)

L is context free only

d)

L is only accpeted by turing machine

87.

Which of the problem is Undeciadable

a)

Membership of CFG's

b)

Ambiguity of Problem of CFGs

c)

Membership of TM

d)

Equivalance of finite state machines

88.

Transition function $\delta$ of NFA i.e Q x $\Sigma$ =

a)

$2^Q$

b)

Q

c)

2XQ

d)

$Q^0$

89.

S-->aBCD

BCD--> DE

D-->aD/a

E--> $\epsilon$ /b

The above grammer is

a)

Type 0 but not type 1

b)

Type 1 but not type 2

c)

Type 2 but not type 3

d)

Type 0,1,2,3

90.

L1 is a Recusive and L2 is Recursive enumerable but not recursive language. Which of the following is True?

a)

Homomorphism of L1 is Resursive

b)

complement of L2 is Recursive enumerable

c)

complement of L1 is Recursive

d)

Homomorphism of L2 is not Resursive enumerable

91.

L1 is a Recusive and L2 is Recursive enumerable but not recursive language. Which of the following is False?

a)

L1 is Recursive Enumerable language

b)

Kleen Clousre of L1 is Recursive

c)

Kleen Clousre of L2 is Recursive

d)

Kleen Clousre of L2 is not Recursive enumerable

92.

L1, & L2 are RL and DCFL . Which of the following is True

a)

L1 $\cup$ L2 is not DCFL

b)

L1 $\cap$ L2 is not DCFL

c)

L1 $\cup$ L2 is CFL

d)

none of the above

93.

Which of the follwing is Equivalent to RE: $L^+$ + $\epsilon$

a)

Kleen closure $\left(\epsilon\right)$

b)

Positive closure (L)

c)

Kleen closure (Kleen closure (L))

d)

Postive closure (L)

94.

Which of the following Statement is True

a)

L is language is accepted by PDA it means it is a Regular Grammar

b)

L is language is accepted by Finite State automata it means it is a Context sensitive Grammar

c)

L is language is accepted by Finite State automata it means it is a Context Free Grammar

d)

L is language is accepted by PDA it means it is a Context Free Grammar

95.

Which of the following problem is undecidable ?

a)

Membership problem for CFG

b)

Ambuguity of Finite state machine

c)

Equivalent of CFL

d)

Totally of DCLF

96.

$0^p1^q0^r,\ where\ p=q\ =r,\ and\ pqr\ge0$ , Which of the following is true

a)

It is accepted by Finite state machine

b)

it is accepted by PDA

c)

It is accpeted NPDA

d)

It is accepted by Turing Machine

97.

if L and compliment of L is CFL, then L is not

a)

Regular

b)

Context Sensitive

c)

Context Free

d)

Recursive language

98.

L1 and L2 is regular language, then

a)

L1 $\cup$ L2 is not Regular

b)

L1 $\cap$ L2 is not Regular

c)

U-L2 is regular, where U is universal

d)

$R1^+$ is not Regular

99.

L1={10,01,110}, L2={ $\epsilon$ + 101} then L1L2 is

a)

{ $\epsilon$ , 10101,101110}

b)

{10101,10101}

c)

{10110, 10101}

d)

{10101, 101110}

100.

Recursive Enumerable are

a)

is a Type 0

b)

subset of CFL

c)

recognized by Turing machine

d)

all of the above

101.

Which of the problems are unsolvable?

a)

a) Halting problem

b)

b) Boolean Satisfiability problem

c)

c) Both (a) and (b)

d)

d) None of the mentioned

102.

Which of the following a turing machine does not consist of?

a)

a) input tape

b)

b) head

c)

c) state register

d)

d) none of the mentioned

103.

A turing machine that is able to simulate other turing machines:

a)

a) Nested Turing machines

b)

b) Universal Turing machine

c)

c) Counter machine

d)

d) None of the mentioned

104.

If d is not defined on the current state and the current tape symbol, then the machine

a)

a) does not halts

b)

b) halts

c)

c) goes into loop forever

d)

d) none of the mentioned

105.

Which of the following are the models equivalent to Turing machine?

a)

a) Multi tape turing machine

b)

b) Multi track turing machine

c)

c) Register machine

d)

d) All of the mentioned

106.

A turing machine operates over:

a)

a) finite memory tape

b)

b) infinite memory tape

c)

c) depends on the algorithm

d)

d) none of the mentioned

107.

Which of the functions are not performed by the turing machine after reading a symbol?

a)

a) writes the symbol

b)

b) moves the tape one cell left/right

c)

c) proceeds with next instruction or halts

d)

d) none of the mentioned

108.

Turing machine can be represented using the following tools:

a)

a) Transition graph

b)

b) Transition table

c)

c) Queue and Input tape

d)

d) All of the mentioned

109.

Statement 1: Multitrack Turing machine.

Statement 2: Gamma is Cartesian product of a finite number of finite sets.

Which among the following is the correct option?

a)

a) Statement 1 is the assertion and Statement 2 is the reason

b)

b) Statement 1 is the reason and Statement 2 is the assertion

c)

c) Statement 1 and Statement 2 are independent from each other

d)

d) None of the mentioned

110.

According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable language?

a)

a) Type 0

b)

b) Type 1

c)

c) Type 2

d)

d) Type 3

111.

Which of the following statements are false?

a)

a) A multi track turing machine is a special kind of multi tape turing machine

b)

b) 4-heads move independently along 4-tracks in standard 4-tape turing machine

c)

c) In a n-track turing machine, n head reads and writes on all the tracks simultaneously.

d)

d) All of the mentioned

112.

A multitape turing machine is ________ powerful than a single tape turing machine.

a)

a) more

b)

b) less

c)

c) equal

d)

d) none of the mentioned

113.

Which of the following is/are not an application of turing machine?

a)

a) Language Recognization

b)

b) Computers of functions on non negative numbers

c)

c) Generating devices

d)

d) None of the mentioned

114.

Which of the following cannot be a possibility of a TM while it processes an input?

a)

a) Enters accepting state

b)

b) Enters non-accepting state

c)

c) Enters infinite loop and never halts

d)

d) None of the mentioned

115.

Pick the odd one out.

a)

a) Subroutines

b)

b) Multiple tracks

c)

c) Shifting over

d)

d) Recursion

116.

Which among the following is not true for 2-way infinte TM?

a)

a) tape in both directions

b)

b) Leftmost square not distinguished

c)

c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.

d)

d) None of the mentioned

117.

For the following language, an enumerator will print:

L={aⁿbⁿ|n>=0}

a)

a) aⁿbⁿ

b)

b) {ab, a²b², a³b³, …}

c)

c) {e, ab, a²b², a³b³, …}

d)

d) None of the mentioned

118.

A man said to a lady, “Your mother’s husband’s sister is my aunt”. How is that lady related to that man?

a)

(A) Daughter

b)

(B) Grand-daughter

c)

(C) Mother

d)

(D) Sister

119.

If X is brother of the son of Y’s son, how is X related to Y?

a)

(A) Son

b)

(B) Brother

c)

(C) Cousin

d)

(D) Grand-Son

120.

Pointing to a photograph, a man said, “I have no brother or sister but that man’s father is my father’s son”. Whose photograph was it?

a)

(A) His son’s

b)

(B) His father's

c)

(C) His nephew’s

d)

(D) His own

121.

Which of the following statement is wrong?

a)

Every recursive language is recursively enumerable

b)

A language is accepted by FA if and only if it is context free

c)

Recursive languages are closed under intersection

d)

A language is accepted by FA if and only if it is right linear

122.

Reursive Language has --------------------------------------

a)

Turing Machine

b)

No Turing Machine

c)

PDA

d)

FA

123.

Union of two REL will be ----------------------------------------------

a)

Recursive

b)

REL

c)

Partially Recursive

d)

None

124.

Complement of Recursive language will be ---------------------------

a)

REL

b)

Recursive

c)

Non Recursive

d)

none

125.

The intersection of two Recursive Language will be

a)

Recursive

b)

Recursively Enumerable

c)

Non-Recursive

d)

Partially Reccursive

126.

REL may or may not halt for Strings that are in Language L

a)

True

b)

False

127.

Decidable problems are ----------------------

a)

Recursive

b)

Recursively Enumerable

c)

Undecidable

d)

non Recursive

128.

Semi Decidable Problems are ------------------------

a)

Recursive

b)

Recursively Enumerable

c)

Non-Recursive

d)

None of the above

129.

If Turing Machine not able to decide the Problem P, that comes under the category ---------- Problem

a)

Decidable

b)

Semi Decidable

c)

Undecidable

d)

None

130.

Turing Machine will always halt for -------------------- Language

a)

Recursive

b)

REL

c)

Non-Recursive

d)

Undecidable

131.

Recursively Enumerable Language may or may not halt for the string w that are not in Language L.

a)

True

b)

False

132.

This is an example of a _______ problem.

a)

decidable

b)

undecidable

c)

polynomial hard

d)

polynomial incomplete

133.

"Given two numbers x and y, does x evenly divide y?" This is called a _______ problem.

a)

decision

b)

undecidable

c)

polynomial hard

d)

polynomial incomplete

134.

On the APCSP exam, you need to explain the existence of undecidable problems in computer science (Don't need to know whether a given problem is solvable or unsolvable.) Which of the following are true?

a)

An undecidable problem may have instances that have an algorithmic solution that solves all instances of the problem.

b)

A decidable problem is one in which an algorithm can be constructed to answer "yes" or "no" for all inputs (e.g., "is the number even?").

c)

An undecidable problem is one in which no algorithm can be constructed that always leads to a correct yes-or-no answer. (Don't need to know if a problem is undecidable.)

d)

The Halting problem is decidable.

135.

When using mathematical induction to prove : $\sum_{i=1}^ni^2=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$ . In step #2, after you have made your assumption, what are you trying to prove? (What is your goal?)

a)

$\sum_{i=1}^{k+1}i^2=\frac{\left(k\right)\left(k+1\right)\left(2k+1\right)}{6}+\left(k+1\right)^2$

b)

$S_{k+1}=\frac{k\left(k+1\right)\left(2k+1\right)}{6}$

c)

$\sum_{i=1}^{k+1}i^2=\frac{\left(k+1\right)\left(k+2\right)\left(2k+3\right)}{6}$

d)

$S_{k+1}=\left(k+1\right)^2$

136.

A counterexample is ...

a)

a conclusion based on repeated observation of a pattern

b)

a hypothesis made given some information on a repeated pattern

c)

used to disprove a general rule

d)

used to affirm our initial guess

137.

1 + 3 + 5 + 7 + . . . + (2n − 1) = n²
On the basis of this assumption,
[The statement is true for n = k:
1 + 3 + 5 + 7 + . . . + (2k − 1) = k²]
What must we show?

a)

The statement is true for n = 1:
2x1 − 1 = 1²

b)

The statement is true for n = k:
1 + 3 + 5 + 7 + . . . + (2k − 1) = k²

c)

The statement is true for n = k + 1:
1 + 3 + 5 + 7 + . . . + (2k − 1) + (2k + 1) = (k + 1)²

138.

The sum of the first n odd numbers is equal to the n^th square.
1 + 3 + 5 + 7 + . . . + (2n − 1) = n²

To prove this by mathematical induction, what will be the induction assumption?

a)

The statement is true for n = k:
1 + 3 + 5 + 7 + . . . + (2k − 1) = k²

b)

The statement is true for n = 1:
2x1 − 1 = 1²

c)

The statement is true for n = k + 1:
1 + 3 + 5 + 7 + . . . + (2k − 1) + (2k + 1) = (k + 1)²

139.

The second part (If the statement is true for n = k, then it will be true for its successor, k + 1) contains the induction assumption. What is it?

a)

If the statement is true for n = k, then it will be true for its successor, k + 1.

b)

The statement is true for n = k.

c)

The statement is true for n = k+1.

140.

According to the principle of mathematical induction, to prove a statement that is asserted about every natural number n, there are two things to prove. What is the first?

a)

The statement is true for n = 1.

b)

The statement is true for n = k.

c)

The statement is true for n = k+1.

141.

1. Write regular expression for All the words of a language with alphabets {a,b,c} that begins with an ‘a’ or a ‘c’ and then followed by some number of b’s.

a)

(a+c)b

b)

((a+c)b)*

c)

((a+c)*b)*

d)

(a+c)b*

142.

2. Write regular expression for all the words of a language with alphabets {a,b} that contains all the strings of a’s and b’s of length exactly three.

a)

(a+b)3

b)

(a3+b3)

c)

(3a+3b)

d)

(a+b)

143.

3. Write regular expression for All the words of a language with alphabets {a,b} that begin with a and end with b

a)

= ab(a+b)*ab

b)

= a*(a+b)* b*

c)

a(a+b)* b

d)

= a(a+b) b

144.

4. Write regular expression for all the words of a language with alphabets {a,b} that begin with a

a)

a (a+b)*

b)

a* (a+b)*

c)

a (a+b)

d)

a (a*+b*)*

145.

5. Write regular expression for all the words of a language with alphabets {a,b} that ends with aa

a)

(a+b)* a*a

b)

aa

c)

(a+b) aa

d)

(a+b)* aa

146.

6. Write regular expression for all the words of a language with alphabets {a,b} that have atleast one a

a)

(a+b)a(a+b)

b)

(a+b)* a (a+b)*

c)

(a+b)* a* (a+b)*

d)

(a+b)* a

147.

7. Write regular expression for all the words of a language with alphabets {a,b} that have atleast one a and one b

a)

(a+b)* a (a+b)* b (a+b)* + (a+b)*b (a+b)* a (a+b)*

b)

(a+b)* a (a+b)* b (a+b)*

c)

(a+b)*b (a+b)* a (a+b)*

d)

(a+b)* a* (a+b)* b* (a+b)* + (a+b)*b* (a+b)* a* (a+b)*

148.

8. Write regular expression for all the words of a language with alphabets {a,b} that containing any number of a’s and b’s except null string.

a)

(a+b)^*

b)

(a+b)⁺

c)

(a+b)

d)

(a*+b*)

149.

9. Write regular expression for all the words of a language with alphabets {a,b} that have the total number of a’s are divisible by 3

a)

(b*a*b*a*b*a*b*)*

b)

(b*(a+b)*(a+b)*(a+b*)*

c)

(b*ab*ab*ab*)*

d)

((a+b)(a+b)(a+b))*

150.

10. Write regular expression for all the words of a language with alphabets {a,b} that third character from right end of the string is always a.

a)

(a+b)*a (a+b)* (a+b)*

b)

(a+b)*a (a+b) (a+b)

c)

(a+b)*a (a*+b*) (a+b)

d)

(a+b)*a (a+b) (a*+b*)

Theory of Computations -SET 6

Total questions: 150

Worksheet time: 13hrs 30mins

Similar Resources on Wayground