TOC Test 1  GATE CS
Submit Now
0 of 15 questions completed
Questions:
 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
Information
Instructions:
 Total number of questions: 15.
 Total Marks : 25
 Time allotted : 40 minutes.
 no negative marks.
 DO NOT refresh the page.
 To Start test Enter Your Name, email and click on Start.
 To Finish test Click on Submit Now and then Finish.
 After Completing Test, Click on View Question Button to Check Solutions.
 All the best 🙂
Note: Video Solution will be Added Soon
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading...
You must sign in or sign up to start the quiz.
You have to finish following quiz, to start this quiz:
Results
0 of 15 questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 Marks, (0)
Average score 

Your score 

Categories
 TOC 0%

All the Best for GATE 2019.
Pos.  Name  Entered on  Marks  Result 

Table is loading  
No data available  
 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 Answered
 Review

Question 1 of 15
1. Question
1 MarksLet and be two Regular languages. Now consider the following language .
Where is Reverse of String
Which of the following is True regarding language ?
Correct
Explanation : is definitely a Regular language. Since can be written as follows:
And we know that Regular languages are closed under Reversal and Intersection operations.
Incorrect
Explanation : is definitely a Regular language. Since can be written as follows:
And we know that Regular languages are closed under Reversal and Intersection operations.

Question 2 of 15
2. Question
1 MarksConsider the following statements regarding Set of “All Nonregular” languages
1. It is closed under Union.
2. It is closed under Concatenation.
3. It is closed under Complementation.
4. It is an uncountable set.Which of the above statements is/are correct ?
Correct
Explanation
Complement of a Nonregular language is Always a Nonregular language. We can show it by Contradiction. Let L be a NonRegular language and Lc be the complement of L and let L^{c} be Regular. So now Since we know that Regular languages are closed under complementation, (L^{c})^{c} i.e. L must be regular, which is not true.
We can use the above result to show that NonRegular languages are not closed under Union. Let L be a Nonregular language, L^{c} be its complement. We know L L^{c} = , which is Regular.
Set of Nonregular languages is not closed under Concatenation, to show that let’s take Two Nonregular languages as follows :
L1 =
L2 =
L1 and L2 both languages are Nonregular languages (CSL) but is i.e. Regular.
And Since Set of Nonregular languages contain NotRE languages too, So, It is an uncountable set.
Incorrect
Explanation
Complement of a Nonregular language is Always a Nonregular language. We can show it by Contradiction. Let L be a NonRegular language and Lc be the complement of L and let L^{c} be Regular. So now Since we know that Regular languages are closed under complementation, (L^{c})^{c} i.e. L must be regular, which is not true.
We can use the above result to show that NonRegular languages are not closed under Union. Let L be a Nonregular language, L^{c} be its complement. We know L L^{c} = , which is Regular.
Set of Nonregular languages is not closed under Concatenation, to show that let’s take Two Nonregular languages as follows :
L1 =
L2 =
L1 and L2 both languages are Nonregular languages (CSL) but is i.e. Regular.
And Since Set of Nonregular languages contain NotRE languages too, So, It is an uncountable set.

Question 3 of 15
3. Question
1 MarksConsider the following statements :
1. There exists a RE language for which there is No Ambiguous grammar possible.
2. There exists a RE language for which there is No Unambiguous grammar.Which of the above statements is/are correct ?
Correct
Explanation
Statement 1 is correct and the ONLY language, for which it is true, is Empty language. Since Empty language does not contain any string, we can’t make at least Two parse trees for any string in the language.
Statement 2 is also true and such languages are called Inherently ambiguous languages. While some RE languages have both ambiguous and unambiguous grammars, there exist contextfree languages for which no unambiguous grammar can exist. An example of an inherently ambiguous language is the union of with . This set is contextfree, since the union of two contextfree languages is always contextfree. But there is no way to unambiguously parse strings in the (noncontextfree) common subset
Incorrect
Explanation
Statement 1 is correct and the ONLY language, for which it is true, is Empty language. Since Empty language does not contain any string, we can’t make at least Two parse trees for any string in the language.
Statement 2 is also true and such languages are called Inherently ambiguous languages. While some RE languages have both ambiguous and unambiguous grammars, there exist contextfree languages for which no unambiguous grammar can exist. An example of an inherently ambiguous language is the union of with . This set is contextfree, since the union of two contextfree languages is always contextfree. But there is no way to unambiguously parse strings in the (noncontextfree) common subset

Question 4 of 15
4. Question
1 MarksConsider the language
Consider the following sentences about the above language
 is Finite
 The minimal DFA that accepts has 3 states.
 The regular expression for is
 The regular expression for is
Which of the above statements are correct?
Correct
The language consists of all the strings w such that for that string w, abw = wba. So, the Regular expression representing the language L is and the minimal DFA of this language will have 3 states.
Incorrect
The language consists of all the strings w such that for that string w, abw = wba. So, the Regular expression representing the language L is and the minimal DFA of this language will have 3 states.

Question 5 of 15
5. Question
1 MarksConsider the following Two lists of strings over alphabet
The number of different Post Correspondence solutions for the above two lists is _________ .

Question 6 of 15
6. Question
2 MarksWhich of the following is Class of Language is Regular:
A) { wxw^{R}  w,x ∈ {0,1}^{+} }
B) { wxw^{R}∣w,x∈{0,1}^{+ }and x=100 where x denotes length of string x }
C) { wxw^{R}∣w,x∈{0,1}* and x>=100 where x denotes length of string x }
D) { wxw^{R}∣w,x∈{0,1}* and x<=100 where x denotes length of string x }

Question 7 of 15
7. Question
2 MarksConsider the following problems.
 Given a TM M and a string w, does M ever write the Symbol $ on its tape on input w?
 Given a CFG G over {0,1}, does G generate all the strings of the language {0,1}* of length 1050?
 Given a CFG G over {0,1}. does G generate all the strings of the language {0,1}* of length greater than 1050?
 Given a TM M, are there infinitely many TM M’ accepting the same language i.e. L(M) ?
Which of the above Problem is decidable?

Question 8 of 15
8. Question
2 Marks 
Question 9 of 15
9. Question
2 MarksConsider the following language over the alphabet {0,1}.
L={ xyx has even number of 1’s, y has an even number of 0’s}
Which is True for L ?

Question 10 of 15
10. Question
2 MarksLet r, s, t be any three regular expressions. Now consider the following statements:
 If L(r) contains L(t+sr) then it also contains L(s*t)
 If L(r) = L(t+rs) then L(r)=L(s*t)
Which of the following is correct ?

Question 11 of 15
11. Question
2 MarksLet A be any language over .We say that strings x and y in are indistinguishable by A iff for every string z either both xz and yz are in A or both xz and yz are not in A. We write x _{A} y in this case. Notice that the relation _{A }on is an Equivalence relation.
Suppose that ={a,b} and L={a^{n}b^{n } n0}, Now consider the following statements.
 Set L is a subset of one of the equivalence class of relation _{L}
 Let S= {a^{i} i>=0}, then No Two elements of S belongs to same equivalence class of L.
Which of the above statements is/are True?

Question 12 of 15
12. Question
2 MarksConsider the following statements.
 If a DFA M accept any string at all, then it accepts one whose length is less than the number of states in M.
 If a DFA M accepts all the strings of length less than the number of states in M then L(M) is always where is the alphabet.
Which of the above sentences is/are correct ?

Question 13 of 15
13. Question
2 Marks 
Question 14 of 15
14. Question
2 MarksConsider the following languages.
1.
2.
3.
Which of the above languages Satisfy Pumping lemma for Regular languages?

Question 15 of 15
15. Question
2 MarksConsider the following languages.
Which of the above is Not a Regular language?
Correct
Answer : D. All are Regular.
… Though WW is a Standard Nonregular(CSL) language But over Unary alphabet, It is Regular languages. It is just a Set of All Even length Strings.
….. Every String except , can be written in the form ..
…. The language to the left of Union is a Subset of the language to the right of Union.
Incorrect
Answer : D. All are Regular.
… Though WW is a Standard Nonregular(CSL) language But over Unary alphabet, It is Regular languages. It is just a Set of All Even length Strings.
….. Every String except , can be written in the form ..
…. The language to the left of Union is a Subset of the language to the right of Union.