Automata Solved Mcq 4el5

Cs402- Theory of Automata Latest Solved MCQs from Final term Papers

10 june,2011

[email protected]

Latest Mcqs

FINAL TERM

Solved MCQS for final term Question: 1 The production of the form nonterminal →Λ is said to be null production. Ø ► True Page 104 Ø ► False Question: 2 Consider the following GFC : s→aa|bB,a→aa|B,B→aS|Λ here s→aaand A→B are null productions ,while B→Λ is null able production Ø ►false page 105 Ø ►True Question: 3 Which statement is true? Ø The tape of turing machine is infinite. Ø The tape of turing machine is finite. Ø The tape of turing machine is infinite when the language is regular Ø The tape of turing machine is finite when the language is nonregular. Question: 4 The production of the form nonterminal →one nonterminal is called the : Ø Null production Ø Null able production Ø Unit production page105 Ø None of the given Question: 5 For a given input, it provides the compliment of Boolean AND output. Ø NAND box (NOT AND) Ø DELAY box Ø OR box Ø AND box Question: 6 ( Marks: 1 ) - Please choose one Choose the correct statement.

Ø Ø Ø Ø

A Mealy machine generates no language as such A Moore machine generates no language as such A Mealy machine has no terminal state All of these

Question: 7 Let Q and R be expressed by ab*a and (ba)* respectively i.e Q={aa ,aba ,abba ……}and R={Λ,ba baba,bababa…….}..aba is the only word in Q which can make a word in R, because the words in R don,t contain the Ø Ø Ø Ø

Single letter Double letter String Null string

page 84

Question: 8 It delays the transmission of signal along the wire by one step (clock pulse). Ø OR box Ø DELAY box Ø NAND box (NOT AND) Ø AND box Question: 9 To describe the complement of a language, it is very important to describe the ----------- of that language over which the language is defined. Ø String Ø Regular Expression Ø Alphabet Ø Word Question:10 Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called : Ø Non regular language of L Ø Complement of the language L Ø Non of the given Ø All of above Question:11 For the given input, it provides the Boolean OR output Ø DELAY box Ø AND box Ø NAND box (NOT AND) Ø OR box Question: 12 For the given input, AND box provides the Boolean AND output. Ø True

Ø False Question: 13 The current in the wire is indicated by 1 and 0 indicates the absence of the current. Ø True Ø False Question: 14 If L is a regular language ,then according to Kleene,theorem , there exists an : Ø TG Ø GTG Ø FA page77 Ø Non of the given Question: 15 Any language that can not be expressed by a RE is said to be regular language. Ø True Ø False Question: 16 and r2 = ( a + b) then the language (aa + bb)(a + b) will be generated by Ø Ø Ø Ø

(r1 + r2) (r2)(r1) (r1)* (r1)(r2)

Question: 17 If L1 and L2 are regular languages is/are also regular language(s). Ø Ø Ø Ø

L1 + L2 L1L2 L1* All of above

Page 70

Question: 18 Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L, is called Complement of the language L, denoted by Lc or L’. True False NO19: For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = L Ø True Page 71 Ø False Question: 20 If L is a regular language then, Lc is also a _____ language.

Ø Ø Ø Ø

Regular Non-regular Regular but finite None of the given

Question: 21 If an effectively solvable problem has answered in yes or no, then this solution is called --------Ø Decision problem Ø Decision method Ø Decision procedure Ø Decision making Question: 22 There is an approach in defining the quotient of regular languages ie the language Q is said to be quotient of two regular languages P and R, denoted by Q=R/P if : Ø PQ=R Ø R=PQ Ø QR=P Ø Non of above Question: 23 consider a language L defined over an alphabet ∑ if two strings x and y defined over ∑ are run over an FA accepting the language L,then x and y are said to belong to the same ………. if they end in the same ……. Ø Class ,state Ø Final ,infinite Ø Regular ,nonregular Ø All of Above Question:24 If L is a regular language then, --------- is also a regular language. Ø Lm Ø Ls Ø Lx Ø Lc Question:25 Converting each of the final states of F to non-final states and old non-final states of F to final states, FA thus obtained will reject every string belonging to L and will accept every string, defined over Σ, not belonging to L. is called Ø Ø Ø Ø

Complement of L Finite Automata of L Transition Graph of L Regular expression of L

Question: 26 If L1 and L2 are two regular languages, then L1 U L2 is not a regular. Ø True Ø False

Question:27 L= language of words containing even number of a’s. Regular Expression is Ø Ø Ø Ø

(a+b)*aa(a+b)* (b+ab*a)* a+bb*aab*a (a+b)*ab(a+b)*

Question:28 The regular expression defining the language L1 U L2 can be obtained, converting and reducing the previous ------------- into a ------------ as after eliminating states. Ø Ø Ø Ø

GTG, TG FA, GTG FA, TG TG, RE

Question: 29 The language that can be expressed by any regular expression is called a Non regular language. True False Page 76 Question:30 Please choose one Choose the incorrect statement: Ø (a+b)*aa(a+b)* generates Regular language. Ø A language consisting of all strings over ∑={a,b} having equal number of a’s and b’s is a regular language Ø Every language that can be expressed by FA can also be expressed by RE Ø None of these

Question: 31 The languages -------------- are the examples of non regular languages Ø EVEN-EVEN and PRIME Ø PALINDROME and PRIME. Page 76 Ø PALINDROME and EVEN-EVEN Ø FACTORIAL and SQURE

Question: 32 De-Morgan's law for sets is expressed by, Ø ( L1c ∩ L2 c )c = L1c ∩ L2 c Ø ( L1c ∩ L2 c )c = L1 ∩ L2 Ø ( L1c ∩ L2 c )c = L1 ∪ L2 Ø ( L1c ∩ L2 c )c = L1c ∩ L2 c

Question: 33 Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ* such that all the strings of the form xy n z for n=1,2,3, … are the words in L. called Complement of L Ø Ø Ø Ø

Pumping Lemma Kleene’s theorem None of the given 1,2 both

Page 77

Question: 34 Languages are proved to be regular or non regular using pumping lemma. Ø True Ø False Question:35 ------------------- is obviously infinite language. Ø Ø Ø Ø

EQUAL-EQUAL EVEN-EVEN PALINDROME FACTORIAL

Page 80

Question: 36 If L1 and L2 are expressed by regular expressions r1 and r2, respectively then the language expressed by r1 + r2 will be _________ Ø Ir-regular Ø Can’t be decided Ø Regular language Page 77 Ø Another Language which is not listed here Question: 37 Let L be an infinite language accepted by a language accepted by a finite automaton with N states , then for all words W in L that have length more than N there are strings x,y and Z (y being non null string)and length (x)+length (y)≤Ns.t.W=xyz and all strings of the form xynz are in L for n=1,2,3……….. Ø True Page 80

Ø False Question: 38 If, two strings x and y, defined over Σ, are run over an FA accepting the language L, then x and y are said to belong to the same class if they end in the same state, no matter that state is final or not. Ø True Ø False Question: 39 Myhill Nerode theorem is consisting of the followings. Ø L partitions Σ* into distinct classes. Ø If L is regular then, L generates finite number of classes. Ø If L generates finite number of classes then L is regular. Ø All of above Page 80 Question:40 The language Q is said to be quotient of two regular languages P and R, denoted by--- if PQ=R. Ø Ø Ø Ø

R=Q/P Q=R/P Q=P/R P=R/Q

Page 83

Question:41 If two languages R and Q are given, then the prefixes of Q in R denoted by Pref(Q in R). Ø True Page 83 Ø False Question:42 Let Q = {aa, abaaabb, bbaaaaa, bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa} Pref (Q in R) is equal to Ø {b,bbba,bbbaaa}, Page 83 Ø {b,bba,bbaaa} Ø {ab,bba,bbbaa} Ø {b,bba,bbba} Question: 43 If R is regular language and Q is any language (regular/ non regular), then Pref (Q in R) is ---------. Ø Non-regular Ø Equal Ø Regular Page 84 Ø Infinite Question: 44 The regular expression thus obtained if contains at least one word then the language is not empty

otherwise the language is : Ø Ø Ø Ø

Regular No regular Empty Page 85 Non of the above

Question: 45 "CFG" stands for _________ : Ø Ø Ø Ø

Context Free Graph Context Free Grammar Page 92 Context Finite Graph Context Finite Grammar

Question:46 The langue generated by CFG is called Context free language (CFL) Ø False Ø True Question:47 ___________ states are called the halt states. Ø Ø Ø Ø

ACCEPT and REJECT ACCEPT and READ ACCEPT AND START ACCEPT AND WRITE

Question:48 If a regular expression contains * then it may define an infinite language ,with exception Λ*as Λ*= Λ e.g. Ø (Λ+a Λ*)(Λ*+Λ) * defines finite language. While (Λ+a Λ*)*(Λ*+Λ) *defines an finite language. Ø True Ø False Page 90 Question:49 The part of an FA, where the input string is placed before it is run, is called Ø Ø Ø Ø

State Transition Input Tape Page 110 Output Tape

Question: 50 TM is more powerful than FSM because Ø The tape movement is confined to one direction Ø It has no finite state control Ø It has the capability to arbitrary long sequences of input symbols Ø None of these NO51: In new format of an FA This state is like dead-end non final state: Ø ACCEPT Ø REJECT Page 110 Ø STATR Ø READ NO52: For language L defined over {a, b}, then L partitions {a, b}* into …… classes Ø Infinite Ø Finite Ø Distinct Ø Non-distinct NO53 := language of words containing even number of a’s. Regular Expression is Ø Ø Ø Ø

(a+b)*aa(a+b)* (b+ab*a)* a+bb*aab*a (a+b)*ab(a+b)*

No 54:All NonNull words of the CFL can be generated by the corresponding CFG which is in CNF i.e the grammar in CNF will generate the same language except the : Ø Ø Ø Ø

string regular language null string . non of above

NO55: The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree . Ø Ø Ø Ø

CFL CFG Page 98 GTG None of the given

NO56 : Between the two consecutive ts on a path Ø Ø Ø Ø

One character can be pushed and one character can be popped Any no. of characters can be pushed and one character can be popped One character can be pushed and any no. of characters can be popped Any no. of characters can be pushed and any no. of characters can be popped

NO57: In pumping lemma theorem (x y^n z) the range of n is: Ø Ø Ø Ø

n=1, 2, 3, 4………. Page 77 n=0, 1, 2, 3, 4………. n=…….-3,-2,-1, 0, 1, 2, 3, 4…… n=…….-3,-2,-1, 1, 2, 3, 4……

NO58: TM is more powerful than FSM because Ø The tape movement is confined to one direction Ø It has no finite state control Ø It has the capability to arbitrary long sequences of input symbols Ø None of these NO59 : If every production in CFG is one of the following forms Conterminal → semi word Nonterminal→word Then the language generated by that GFC is : Ø Regular Ø Nonregular Ø Finite Ø Infinite NO 60: Then the language generated by that CFG is: Ø Non regular Ø Infinite Ø Regular Page 102 Ø Finite NO 61:The PDA is called non-deterministic PDA when there are more than one out going edges from……… state : Ø START or READ Ø POP or REJECT Ø READ or POP Page 116 Ø PUSH or POP NO:62 Identify the TRUE statement: Ø A PDA is non-deterministic, if there are more than one READ states in PDA Ø A PDA is never non-deterministic Ø Like TG, A PDA can also be non-deterministic Page 116 Ø A PDA is non-deterministic, if there are more than one REJECT states in PDA NO:63 the language Q is infinite. Ø True Page 134 Ø False Left hand side of a production in CFG consists of:

Ø Ø Ø Ø

One terminal More than one terminal One non-terminal Terminals and non-terminals

Page 64:

NO65: it is very important to determine which sequences of rows do correspond to possible paths through the: Ø CFG Ø CFL Ø PDA Page 128 Ø TAPE NO: 66 : The following problem(s) ------------- is/are called decidable problem(s). Ø The two regular expressions define the same language Ø The two FAs are equivalent Ø Both a and b Ø None of given NO67: Before the CFG corresponding to the given PDA is determined,the PDA is converted in to the standard form which is called the: Ø Standard form Ø Conversion form Page 108 Ø Left most derivation Ø None of them NO: 68 The deviation of the word W generated by a CFG, such that at each step ,a production is applied to the left most nonterminal in the working string is said to be Ø Ø Ø Ø

Left most terminal Left most deviation : Page 108 None of these A ,B both

NO 69: To examine whether a certain FA accepts any words, it is required to seek the paths from ------ state. Ø Final to initial Ø Final to final Ø Initial to final Ø Initial to initial NO 70: The high level language is converted into assembly language codes by a program called compiler. Ø TRUE Ø FALSE NO 71: Grammatical rules which involve the meaning of words are called ---------------

Ø Semantics

Page 92

Ø Syntactic Ø Both a and b Ø None of given NO72: Choose the correct statement. A Mealy machine generates no language as such A Moore machine generates no language as such A Mealy machine has no terminal state All of these

NO: 73 Grammatical rules which do not involve the meaning of words are called --------------Ø Semantics Ø Syntactic Page 92 Ø Both a and b Ø None of given NO74: - Please choose one The word ‘formal’ in formal languages means Ø They are unnecessary, in reality Ø Only the form of the string of symbols is significant Ø The symbols used have well defined meaning Ø None of these NO: 75 ……………… is a place where the input letters can be placed until these letters are referred again. It can store as many letters as one can in a long column . Ø STACK Ø POP AND STACK Ø PUSHDOWN STACK Page 112 Ø None of above NO 76: Consider the language L of strings, defined over Σ = {a,b}, ending in a ► There are finite many classes generated by L, so L is regular ► There are infinite many classes generated by L, so L is regular ► There are finite many classes generated by L, so L is non-regular ► There are infinite many classes generated by L, so L is non-regular

NO77: The symbols that can’t be replaced by anything are called ----------------Ø Productions Ø Terminals Page 92 Ø Non-terminals Ø All of above

NO78: “One language can be expressed by more than one FA”. This statement is ______ Ø True Ø False Ø Some times true & sometimes false Ø None of these NO: 79 The symbols that must be replaced by other things are called __________ Ø Productions Ø Terminals Ø Non-terminals Page 92 Ø None of given NO 80: Which of the following statement is NOT true: Ø Ø Ø Ø

FA can be considered to be an NFA FA can be considered to be an NFA with null string NFA can be considered to be an TG TG can be considered to be an NFA

NO 81: Let FA 3 be an FA accepting L1∩L2 then the initial stat of FA3 must be correspond to the initial state of………. and initial state of ……… p 74 Ø FA3, FA2 Ø FA1 , FA2 Ø FA1,FA3 Ø None of the given NO82: If r1 = (aa + bb) and r2 = ( a + b) then the language (aa + bb)(a + b) will be generated by Ø (r1)(r2) Ø (r1 + r2) Ø (r2)(r1) Ø (r1)* NO83: The grammatical rules are often called_____________ Ø Productions Page 92 Ø Terminals Ø Non-terminals Ø None of given NO 84: Does the empty string match the regular expression |y+a|? Ø Yes Ø No NO 85 The terminals are designated by ________ letters, while the non-terminals are designated by ________ letters.

Ø Ø Ø Ø

Capital, bold Small, capital Capital, small Small, bold

Page 92

NO86: FA corresponding to an NFA can be built by introducing a state corresponding to the combination of states, for a letter having Choices: Ø no transition at certain state Ø one transition at certain state Ø more than one transitions at certain state Ø none of the given options NO:87 Σ = {a,b} Productions S→XaaX X→aX This grammar defines the language expressed by___________ Ø (a+b)*aa(a+b)* Page 94 Ø (a+b)*a(a+b)*a Ø (a+b)*aa(a+b)*aa Ø (a+b)*aba+b)*

X→bX

X→Λ

NO 88: Which statement is true: Ø ► The tape of turing machine is infinite. Ø ► The tape of turing machine is finite. Ø ► The tape of turing machine is infinite when the language is regular Ø ► The tape of turing machine is finite when the language is nonregular. NO89 : The language generated by __________ is called Context Free Language (CFL). Ø FA Ø TG Ø CFG Page 93 Ø TGT NO 90: Let A = {0, 1}. The number of possible strings of length ‘n’ that can be formed by the elements of the set A is: Ø n! Ø n2 Ø nm Ø 2n NO : 91 S → aXb|bXa X → aX|bX|Λ The given CFG generates the language of strings in English __________ Ø Beginning and ending in different letters Page 96 Ø Beginning and ending in same letter

Ø Having even-even language Ø None of given NO92: Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression. This statement is: Ø Depends on the language Ø None of the given options Ø True Ø False

NO 93: The CFG is said to be ambiguous if there exists atleast one word of its language that can be generated by the different production trees, Ø TRUE Page 100 Ø FALSE NO 94: The language generated by that CFG is regular if _________ Ø Ø Ø Ø

No terminal → semi word No terminal → word Both a and b Page 102 None of given

NO95: A regular language: Ø Must be finite Ø Must be infinite Ø Can be finite or infinite Ø Must be finite and cannot be infinite NO96: The production of the form non terminal → Λ is said to be null production . Ø TRUE Page 104 Ø FALSE NO 97: Who did not invent the Turing machine? Ø Alan Turing Ø A. M. Turing Ø Turing Ø None of these NO: 98

A production is called null able production if it is of the form N → Λ

Ø TRUE Ø FALSE

Page 105

NO99: A DFA with n states must accept at least one string of length greater than n.

Choices: Ø True Ø False NO100: For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the same. Choices: Ø True Ø False NO101: Choose the right option: (2) In a Mealy machine, the set of letters and the set of output characters must be same In a Mealy machine, the set of letters and the set of output characters may not be same B only A only

No102 :

- Please choose one

a

b

X1–

b X2+

a Above given FA corresponds RE r. then FA corresponding to r* will be z1± a

b b

a

z3+

z2 b

This statement is True Page 42 False Depends on language None of these NO103 : - Please choose one

a

aa,bb ±

aa,bb ab,ba

ab,ba

Above given TG has _____________ RE. (aa+aa+(ab+ab)(aa+ab)*(ab+ba))* (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

Page 26

(aa+bb+(ab+ba)(aa+bb)(ab+ba))* None of these

NO104: - Please choose one Like TG, a PDA can also be non-deterministic True False

NO105 :- Please choose one

:

The above machine is a/anTG ___________ http://vustudents.ning.com Finite Automata Turing machine Page 148 FA TG NO106: In FA, if one enters in a specific state but there is no way to leave it, then that specific state is called : Dead State Waste Basket Davey John Locker All of these NO107: - Please choose one In CFG, the symbols that can’t be replaced by anything are called___ Ø Terminal

Ø Non-Terminal Ø Production Ø All of given NO108: - Please choose one Which of the following is NOT a regular language? Ø Ø Ø Ø

String of 0’s whose length is a perfect squere Set of all palindromes made up of 0’s and 1’s String of 0’s whose length is a prime number All of the given options

NO109: - Please choose one Choose the incorrect (FALSE) statement Ø A Mealy machine generates no language as such Ø A Mealy machine has no terminal state Ø For a given input string, length of the output string generated by a Moore machine is not more than the length of the output string generated by that of a Mealy machine . Page 62 Ø All of these NO110: - Please choose one Pumping lemma is generally used to prove that ► A given language is infinite ► A given language is not regular : Page 77 ► Whether two given regular expressions of a regular language are equivalent or not ► None of these NO111:- Please choose one Which of the following is a regular language? Ø String of odd number of zeroes Ø Set of all palindromes made up of 0’s and 1’s Ø String of 0’s whose length is a prime number Ø All of these NO112 : lemma is generally used to prove that Ø A given language is infinite Ø A given language is not regular Page 78 Ø Whether two given regular expressions of a regular language are equivalent or not Ø None of these NO113: language can be expressed by more than one FA”. This statement is ______ Ø True Ø False Ø Some times true & sometimes false Ø None of these

NO114: language: Ø Must be finite Ø Must be infinite Ø Can be finite or infinite Ø Must be finite and cannot be infinite NO115 : enters in a specific state but there is no way to leave it, then that specific state is called Ø Dead State Ø Waste Basket Ø Davey John Locker Ø All of these NO116: symbols that can’t be replaced by anything are called___ Ø Terminal Page 92 Ø Non-Terminal Ø Production Ø All of given NO117: following is NOT a regular language? Ø String of 0’s whose length is a perfect squere Ø Set of all palindromes made up of 0’s and 1’s Ø String of 0’s whose length is a prime number Ø All of the given options NO118: Left hand side of a production in CFG consists of Ø One terminal Ø More than one terminal Ø One non-terminal Ø Terminals and non-terminals Page 92 NO119: One language can be expressed by more than one FA”. This statement is ______ Ø True Ø False Ø Some times true & sometimes false Ø None of these Ø NO120: invent the Turing machine? Ø Alan Turing Ø A. M. Turing Ø Turing Ø None of these ‘NO121: formal’ in formal languages means Ø The symbols used have well defined meaning Ø They are unnecessary, in reality Ø Only the form of the string of symbols is significant

Ø None of these NO122: TM is more powerful than FSM because Ø The tape movement is confined to one direction Ø It has no finite state control Ø It has the capability to arbitrary long sequences of input symbols Ø None of these NO123: A program which is the set of rules which show that which state is to be entered when a letter is read form the : Ø TAPE Page 147 Ø HALT Ø TM Ø None of above NO124: The process of finding the derivation of word generated by particular grammar is called : Ø PLUS TIMING Ø Parsing Page 142 Ø HALT Ø All of above NO125: For a non regular language there exist …… FA: Ø NO Ø Yes NO126: Bottem up parsing can be determined similar to that of TOP Down parsing with the change that in this case ,the process is started with the given string and the tree is extended till “S “is Regular Ø Non regular Ø Obtain Page 146 Ø Finite NO127: A production in CFG consists of: Ø One terminal Ø More than one terminal Ø One non-terminal Ø Terminals and non-terminals NO128: If L1 and L2 are regular languages is/are also regular language(s). o L1 + L2 o L1L2 o L1* o All of above NO129: Between the two consecutive ts on a path Ø One character can be pushed and one character can be popped

Ø Any no. of characters can be pushed and one character can be popped Ø One character can be pushed and any no. of characters can be popped Ø Any no. of characters can be pushed and any no. of characters can be popped NO131: Language which are context –free are called Non –CFL: Ø True Ø False Page 132 NO132: The following problem(s) ------------- is/are called decidable problem(s). The two regular expressions define the: Ø same language Ø The two FAs are equivalent Ø Both a and b Ø None of given NO133: If F accept an ………….. language then there are some words w.s.t N≤ length (w) <2n : Ø Regular Ø Finite Ø Infinite Page 91 Ø None of given NO134:If an FA has N state then it must accept the word of length: Ø N2 Ø N-1 Ø n+1 Ø all of above NO135: The values of input (say a & b) does not remain same in one cycle due to Ø tape Ø halt Ø clock pulse Ø start

NO136: Consider the following CFG s→aS|bS|aaS|Λ can be observed that the word aaa can be derived from more than: Ø one production tree Page 101 Ø two producton tree Ø Total language tree Ø All of above

NO137: One language can have ……… CFG(s) Ø At least one Ø At least two Ø At least three Ø None of them NO138: The reverse of the string sbfsbb over { sb, f, b} Ø (bsbfsb) Ø bfsbs Ø sbbfsb Ø bbfsb NO139: CFG is said to be a regular grammar if it generates the regular language i.e.a CFG is said to be a regular grammar in which each production is one of the: Ø Ø Ø Ø

Three forms One form Four forms Two forms Page 102

NO140: If L1 and L2 are regular languages then which statement is NOT true? Ø (L1/L2 is always regular) Ø L1+L2 are always regular Ø L1*l2 are always regular Ø None of them NO141: If the intersection of two regular languages is regular then the complement of the intersection of these two languages is also regular: Ø False Ø True NO142: the moment a final state of ……….. FA is entered ,the possibility of the initial state of ……….. FA will be included as well: Ø first ,third Ø first ,second Page 39 Ø second ,third Ø all of above Ø NO143: Any word generated by given CFG cannot also be expressed by Syntax tree or Generation tree or Derivation tree as well Ø true Ø false NO144: According to Mayhill Nerode theorem, if L generates finite no. of classes then L is..... Ø Regular

Ø Nonregular Ø Infinite Ø Finite NO145: L is a regular language so by kleene,s theorem ,there exists an: Ø FA Page 71 Ø GTG Ø TG Ø CNF NO146: The language generated by the CFG is called the language ……by the CFG Ø Produced Ø Null string Ø Pumping lemma Ø Non of then

NO147: In CFG, the symbols that cannot be replaced by anything are called: Ø None terminals Ø Infinite Ø Finite Ø Terminals NO148: The production S --> SS | a | b | ^ can be expressed by RE: Ø (a+b)+ Ø a-b Ø (a-b)+ Ø None of them NO149: Set of all palindromes over {a,b}is regular Ø (false) Ø (true) NO150: An FA has same initial and final state, then it means that it has no final state. Ø (false) Ø (true) NO151: The same non terminals can be written in single line if they have more than one.......... Ø (Productions) Ø Regular production Ø None regular production NO152: If L1 and L2 are two regular languages then L1∩L2 is also : Ø Regular Page 73

Ø None regular Ø Finite Ø None infinite NO154: For language L defined over {a, b},then L partitions {a, b}* into …… classes: Ø (Distinct) Ø Accept Ø Unit production Ø None of the above NO155: The two FAs are Ø Same Ø Equivalent Page 85 Ø Different Ø None of them NO156:There is at least one production that has one........on its left side: Ø Terminal Ø Infinite Ø None Terminal Ø All of above NO157:The complement of a regular language is also a regular Ø (True) Ø False

Ø NO159: If an effectively solvable problem has answer in yes or no ,then this solution is called : Decision procedure Page 85 Ø Decidable problem Ø Solved able problem Ø All of above NO160: In pref(Q in R) Q is …… to (than) R Ø Q is not equal to R Ø Q is equal to R Ø Q is infinite Ø None of them NO61: For FA corresponding To (L1∩L2c)U (L1c∩L2) the regular expression ca be determined that defines the language accepted by this : Ø TG Ø GFC

Ø FA Ø GTG

Page 85

NO162: a^n b^n generates the ………… language: Ø Non regular languages Ø Regular language Ø Infinite language Ø Finite language NO: 163 (a+b)*a(a+b)*b(a+b)* is the RE of language defined over ={a,b} having at least one a and one b Ø True Page 11 Ø False Such a language does not exist None of these Question No: 164: ( Marks: 1 ) - Please choose one NO164: If r1 = (aa + bb) and r2 = ( a + b) then the language (a + b)* (aa + bb)* will be generated by : Ø Ø Ø Ø

(r2)(r1) (r1 + r2)* (r2)*(r1)* (r1)*

Page 12

Question No 165: ( Marks: 1 ) - Please choose one NO165: In FA starting state is represented by a ________ sign. Ø + Ø Ø * Ø S NO166: If w is large enough word in a CF then w can be decomposed into w =uvwxyz such that all words of the form uvn xynz belong to : Ø CNF Ø L Ø CFL Ø CFG NO167: Can a turing machine's head ever be in the same location in two successive steps? Ø Yes Ø Yes but only in finite languages Ø No Page 150 Ø Yes but only in infinite langauges

NO168: Examin the following CFG and select the correct choice: S→ → AB, A →BSB, B→ → CC C→ → SS A→ → a|b C→ → b|bb Ø abb is a word in the corresponding CFL. Page 139 Ø abb is not the word of corresponding CFL. Ø any word can be accept from the corresponding CFL. Ø Non of these NO169: The production of the form nonterminal →string of two nonterminals is called a: Ø live production Page 132 Ø dead production Ø type of production Ø none of them Question No: 10 ( Marks: 1 ) - Please choose one NO170: Converting the given CFG in CNF is the first rule of _____ Ø CYK algorithm Page 140 Ø CKY algorithm Ø KYC algorithm Ø CNK algorithm Question No: 11 ( Marks: 1 ) - Please choose one NO171: Which statement is true? Ø Ø Ø Ø

The PDA must have one accept state and one reject state The PDA must have one accept state and two reject state The PDA must have two accept state and two reject state There is no reject state in the PDA. Page 124

NO172: Question No: 12 ( Marks: 1 ) - Please choose one If a language can be expressed by a regular expression, then its complement cannot be expressed by a regular expression. This statement is: Ø true Ø False Ø Depends on language Ø None of the given optios NO173: Left hand side of CFG may consist of: Ø One terminal Ø More than one terminal Ø One non-terminal Ø Terminals and non-terminals