Theory of Computation Solved MCQ - Part 2

Given the language L-{ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) b...



Given the language L-{ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

1,2 and 3
2,3 and 4
1,2 and 4
1,3 and 4
      _____________________________________________________________________________________
Push down machine represents

Type 0 Grammar
Type 1 grammar
Type-2 grammar
Type-3 grammar
      _____________________________________________________________________________________
The behavior of a NFA can be stimulated by DFA 

always
sometimes
never
depend on NFA
      _____________________________________________________________________________________


Both statements S1 and S2 are incorrect.
S1 is incorrect and S2 is correct.
S1 is correct and S2 is incorrect.
Both statements S1 and S2 are correct.
      _____________________________________________________________________________________


A
B
C
D
      _____________________________________________________________________________________
Which of the following is not primitive recursive but partially recursive? 

Carnot function
Rieman function
Bounded function
Ackermann function
      _____________________________________________________________________________________

Consider the following grammar.
S ::= AB
A ::= a
A ::= BaB
B ::= bbA
Which of the following is false?


No string produced by the grammar has four consecutive b s
No string produced by the grammar has three consecutive a s
No string produced by the grammar has an odd number of consecutive b s
The length of every string produced by the grammar is even.
      _____________________________________________________________________________________
Set of regular languages over a given alphabet set,is not closed under 

Union
Complementation
Intersection
None of the above
      _____________________________________________________________________________________
Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains

n states
n + 1 states
n + 2 states
2n states
      _____________________________________________________________________________________

LL grammar for the language L = {an bm cn+m | m=0, n=0} is


A
B
C
D
      _____________________________________________________________________________________
The logic of pumping lemma is a good example of 

The pigeon hole principle
Divide and conquer method
Iteration
Recursion
      _____________________________________________________________________________________
If every string of a language can be determined whether it is legal or illegal in finite time the language is called 

Decidable
Undecidable
Interpretive
Non deterministic
      _____________________________________________________________________________________
Context free language can be recognized by 

Finite State Automaton
Linear bounded automaton
Pushdown automaton
Both B and C
      _____________________________________________________________________________________
Fred created a new automaton model which is a push down automaton but with two stacks and the added ability of having commands which do not read input tape but which can pop from one stack and push into the other.This new automaton can recognize (choose strongest result)

Context free language
Context sensitive language
Regular language
Languages recognizable by Turing machine
      _____________________________________________________________________________________

Given the following productions of a grammar :


The language corresponding to the given grammar is a set of even number of a s.
The language corresponding to the given grammar is a set of odd number of a s.
The language corresponding to the given grammar is a set of even number of a’s followed by odd number of b s.
The language corresponding to the given grammar is a set of odd number of a’s followed by even number of b s.
      _____________________________________________________________________________________
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.


A
B
C
D
      _____________________________________________________________________________________


A
B
C
D
      _____________________________________________________________________________________
The regular expression for the following DFA


ab*(b + aa*b)*
a*b(b + aa*b)*
a*b(b* + aa*b)
a*b(b * + aa*b)*
      _____________________________________________________________________________________
FSM can recognize 

Any grammar
Only CFG
Any unambiguous grammar
Only regular grammar
      _____________________________________________________________________________________

Assume statements S1 and S2 defined as :
S1 : L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively.
S2 : The set of all Turing machines is countable. 
Which of the following is true ?


S1 is correct and S2 is not correct.
Both S1 and S2 are correct.
Both S1 and S2 are not correct.
S1 is not correct and S2 is correct.
      _____________________________________________________________________________________
Which of the following is the most general phase structured grammar ?

Regular
Context-sensitive
Context free
None of the above
      _____________________________________________________________________________________
A FSM can be used to add how many given integers? 

1
3
4
5
      _____________________________________________________________________________________

The language accepted by the nondeterministic pushdown automaton


L(abb*a)
{a} U L(abb*a)
L(ab*a)
{a} U L(ab*a)
      _____________________________________________________________________________________
Consider the following statements :
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true ?


I only
I and II
I and III
I and III
      _____________________________________________________________________________________
6 Files F1,F2,F3,F4,F5 and F6 have 100,200,50,80,120,150 records repectively.
In what order should they be sorted so as to optimize activity? Assume each file is accessed with the same frequency.

F3,F4,F1,F5,F6,F2
F2,F6,F5,F1,F4,F3
F1,F2,F3,F4,F5,F6
Ordering is immaterial as all files are accessed with the same frequency
      _____________________________________________________________________________________
Following grammar
S-> bS
S -> b
S -> aA
A -> bA


Type -3 grammar
Type -2 grammar
Type -1 grammar
Type -0 grammar
      _____________________________________________________________________________________

Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is context-free language, then, is ~L also context-free?
3) If L is regular language, then, is ~L also regular?
4) If L is recursive language, then, is ~L also recursive?


1,2,3,4
1,2
2,3,4
3,4
      _____________________________________________________________________________________
The language L={abk|k>=1} is

Type -3 Grammar
Type -2 Grammar
Type -1 Grammar
Type -0 Grammar
      _____________________________________________________________________________________
All strings having equal number of a and b can be recognized by 

DFA
NDFA
PDA
All of these
      _____________________________________________________________________________________
The basic limitation of a FSM is that 

It cannot remember arbitrary large amount of information
It sometimes recognizes grammar that are not regular
It sometimes fails to recognize grammars that are regular
All of the above
      _____________________________________________________________________________________
How many states can a process be in ?

2
3
4
5
      _____________________________________________________________________________________
Which one of the following statement is false ?

Context-free languages are closed under union
Context-free languages are closed under concatenation
Context-free languages are closed under intersection
Context-free languages are closed under Kleene closure
      _____________________________________________________________________________________
Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa


1, 2 and 3
2, 3 and 4
1, 2 and 4
1, 3 and 4
      _____________________________________________________________________________________
Which is not the correct statement(s) ?
(i) Every context sensitive language is recursive.
(ii) There is a recursive language that is not context sensitive.


(i) is true, (ii) is false.
(i) is true and (ii) is true.
(i) is false, (ii) is false.
(i) is false and (ii) is true.
      _____________________________________________________________________________________
A formal grammar is a___________for rewriting strings. 

Set of rules
Set of functions
Both A and B
None of the above
      _____________________________________________________________________________________
Finite automata are used for pattern matching in text editors for 

Compiler lexical analysis
Programming in localized application
Both A and B
None of the above
      _____________________________________________________________________________________
Two finite states are equivalent if they 

Have same number of states
Have same number of edges
Have same number of states and edges
Recognize same set of tokens
      _____________________________________________________________________________________
A PDM behaves like a TM when the number of auxiliary memory it has is 

Zero
One or more
Two or more
None of these
      _____________________________________________________________________________________
Which of the following permanent database that has an entry for each terminal symbol ?

Literal table
Identifier table
Terminal table
Source table
      _____________________________________________________________________________________
The language accepted by finite automata is 

Context free
Regular
Non regular
None of these
      _____________________________________________________________________________________
The following CFG
S®aB|bA, A®a|as|bAA, B®b|bs|aBB
generates strings of terminals that have


Odd number of a’s and odd number of b’s
Even number of a’s and even number of b’s
Equal number of a’s and b’s
Not equal number of a’s and b’s
      _____________________________________________________________________________________
An FSM can be used to add two given integers.This remark is 

True
False
May be true
None of the above
      _____________________________________________________________________________________
Context free languages are not closed under 

Union
Concatenation
Closure
Iteration
      _____________________________________________________________________________________

Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively and transition table as given below :
The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is


5
4
3
2
      _____________________________________________________________________________________
Which of the following is most powerful? 

DFA
NDFA
2PDA
DPDA
      _____________________________________________________________________________________
Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.


1 and 4 only
1 and 3 only
2 only
3 only
      _____________________________________________________________________________________


G1 is ambiguous and G2 is not ambiguous.
G1 is ambiguous and G2 is ambiguous.
G1 is not ambiguous and G2 is ambiguous.
G1 is not ambiguous and G2 is not ambiguous.
      _____________________________________________________________________________________
Finite state machine___________recognize palindromes. 

Can
Cannot
May
May not
      _____________________________________________________________________________________
Given L1=L(a*baa*) and L2=L(ab*). The regular expression corresponding to language L3 = L1/L2 (right quotient) is given by

a*b
a*baa*
a*ba*
None of the above
      _____________________________________________________________________________________
If two finite state machines are equivalent they should have the same number of 

States
Edges
States and edges
None of these
      _____________________________________________________________________________________

TECH$type=three$author=hide

Name

5G Technology,1,Abbreviations,2,Agent AI,1,Agentic Ai,1,AI in Education,1,AI in Healthcare,1,AI in surgery,1,AI Reasoning,1,Algorithm,1,Algorithms,4,android,2,Artemis Mission,1,Artificial Intelligence,5,Artificial Intelligence AI,2,Artificial Neural Networks,1,ASCI and UNI),1,Augmented Reality,1,Automata,3,Blockchain,1,Blockchain Technology,1,C Language,2,C Programming,1,c#,1,C++,2,C++ Programming,1,CakePhp,1,Carbon Neutrality,1,CCNA,1,Cellular Communication,1,Chatgpt,1,Cloud Computing,4,Compiler Construction,1,Compiler Construction Solved MCQs,1,Compiler Design,1,Computer,18,Computer Applications,1,Computer Architecture,3,Computer Arithmetics,1,Computer Basics,1,Computer Codes (BCD,1,Computer Fundamentals,5,Computer Graphics,4,Computer Networking,2,Computer Networks,4,Computer Organization,1,Computer Science,2,Computer Short Cut Keys,1,Computer Short Keys,1,CPU Sceduling,1,Cryptocurrency,1,CSS,1,CSS PMS,1,Current Trends and Technologies,1,Custom Hardware,1,Cyber Security,6,Cybercrimes,1,DALL-E,1,Data Communication,1,Data Privacy,1,Data structures,3,Database Management System,4,DBMS,4,Deadlock,1,DeepSeek,1,Digital Systems,1,Digital Systems Solved MCQs - Part 2,1,Discrete Mathematics,2,Discrete Structure,1,dot Net,1,EBCDIC,1,Edge Computing,2,English,1,Ethical AI and Bias,1,Ethics,1,Explainable AI (XAI),1,File System,1,Flowcharts,1,General Data Protection Regulation GDPR,1,General Knowledge,1,Generative AI,2,Gig Economy,1,Graphics Designing,1,Helping Materials,1,HTML,1,HTML 5,1,hybrid work model,1,Inference Optimization,1,Information Systems,1,Information Technology,1,Inpage,1,intelligence,1,Internet,1,Internet Basics,1,Internet of Things,1,Internet of things IOT,2,IT,1,JavaScript,1,jQuery,1,Language,11,Languages Processor,1,Languge,1,Li-Fi,1,Linux/Unix,2,Magento,1,Memory Management,1,Microprocessor,1,Microsoft PowerPoint,1,MidJourney,1,mindfulness apps,1,MS Access,1,MS DOS,1,MS Excel,1,MS Word,2,Multimodal AI,1,NASA,1,Number System,1,Object Oriented Programming (OOP),1,Object Oriented Programming(OOP),1,Operating System,9,Operating System Basics,1,oracle,2,Others,1,Pakistan,1,PCS,1,PHP,1,PMS,1,Process Management,2,Programming,3,Programming Languages,1,Python,2,python language,1,Quantitative Aptitude,2,Quantum Computing,2,R Programming,1,Ransomware,1,Robotic Process Automation RPA,1,Robotics,2,Ruby Language,1,search engine optimization,1,Semester III,2,seo,1,Sloved MCQs on Microsoft Power Point - updated,1,Software Engineering,3,Solved MCQs of MS Access - Updated,1,Solved MCQs on Computer Fundamentals,1,SpaceX Starship,1,SQL,1,System Analysis and Design,1,Theory of Computation,1,Trends and Technologies,1,Virtual Reality,1,web,1,web Fundamental,1,Web Technologies,2,Web3,1,WEB3 Technology,1,x8086,1,zoology,1,
ltr
item
COMPUTER SCIENCE SOLVED MCQS: Theory of Computation Solved MCQ - Part 2
Theory of Computation Solved MCQ - Part 2
https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibeZW7Xn8df9lPlmsKLnp1lO1KtNcmo05BqUMvZROwH86m5fayLo1jF_XuMPHH-JMuNhsYur1-Db6sDAzLsnShIhIpFKT7UgPzElhV_f-mFDGcflM3sdlx8PXcKCPxD7je79sOh7fwh0k/s1600/automata.png
https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibeZW7Xn8df9lPlmsKLnp1lO1KtNcmo05BqUMvZROwH86m5fayLo1jF_XuMPHH-JMuNhsYur1-Db6sDAzLsnShIhIpFKT7UgPzElhV_f-mFDGcflM3sdlx8PXcKCPxD7je79sOh7fwh0k/s72-c/automata.png
COMPUTER SCIENCE SOLVED MCQS
https://cs-mcqs.blogspot.com/2014/07/theory-of-computation-solved-mcq-part-2.html
https://cs-mcqs.blogspot.com/
https://cs-mcqs.blogspot.com/
https://cs-mcqs.blogspot.com/2014/07/theory-of-computation-solved-mcq-part-2.html
true
1616963833964386058
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content