Solved MCQs on Finite Automata

Finite Automata and Regular Expressions-1 This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Finite Aut...


Finite Automata and Regular Expressions-1


This set of Compilers Multiple Choice Questions & Answers (MCQs) focuses on “Finite Automata and Regular Expressions”.
1. Number of states of FSM required to simulate behaviour of a computer with a memory capable of storing “m” words, each of length ‘n’
a) m x 2^n
b) 2^mn
c) 2^(m+n)
d) All of the mentioned
View Answer
Answer: b
Explanation: For every Data here length is n and memory’s state is defined in terms of power of 2, Here the total memory capability for all the words = mn Hence the number of states is2^mn.
2. An FSM with
a) M can be transformed to Numeral relabeling its states
b) M can be transformed to N, merely relabeling its edges
c) Both of the mentioned
d) None of the mentioned
View Answer
Answer: c
Explanation: The Definition of FSM states that M can be transformed to N by relabeling its states or its edges.
3. Which of the following is right?
a) A Context free language can be accepted by a deterministic PDA
b) union of 2 CFLs is context free
c) The intersection of two CFLs is context free
d) The complement of CFLs is context free
View Answer
Answer: b
Explanation: Context-free languages are closed under the following operations. The Kleene star, the concatenation, the union and the intersection.
4. Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following is true?
a) Only S1 is correct
b) Only S2 is correct
c) Both S1 and S2 are correct
d) None of S1 and S2 is correct
View Answer
Answer: c
Explanation: S1 can be written as (00) ^n where n >= 1. And S2 can be written as (00) ^ (m+n) where m >=2 and n >= 1. S2 can be further reduced to (00) ^x where x >= 3. SO we can write regular grammars for both
G1 -> G100/00 (For S1)
G2 -> G200/000000 (For S2).
5. Which of the following pairs of regular expressions are equivalent?
a) 1(01)* and (10)*1
b) x (xx)* and (xx)*x
c) x^+ and x^+ x^(*+)
d) All of the mentioned
View Answer
Answer: d
Explanation:
Rule (pq)*p=p (qp)*
Therefore–(xx^*) (x*x**)
(xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*)
x+
6. Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.
(a) N^2
(b) 2^N
(c) 2N
(d) N!
View Answer
Answer: b
Explanation: The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ε-moves; that is, it is the set {1, 2, and 3}. A transition from states1, 2, and 3 by input symbol 0 must follow either the arrow from state 1 to 2, or from state 3 to 4. Also, neither state 2 nor 4 have outgoing ε-moves.
7. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
(a) L = O
(b) L is regular but not O
(c) L is context free but not regular
(d) L is not context free
View Answer
Answer: b
Explanation: The grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.
8. Which of the following are not regular?
a) String of )’s which has length that is a perfect square
b) Palindromes Consisting of 0’s 1’s
c) String of 0’s whose length is a prime number
d) All of the mentioned
View Answer
Answer: d
Explanation: Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.
9. If ∑ = {a, b, c, d, e, f} then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is
a) 35
b) 360
c) 49
d) 720
View Answer
Answer: b
Explanation: Here string length is 4 so we create string of length 4 by 6 values firstly we arrange any value by 6 methods. Then Remaining numbers are 5 so we can arrange them by 5 methods then remaining numbers are 4 so we arrange them by 4 methods and then 3.Thus 6*5*4*3=360.
10. Which one of the following statement is FALSE?
a) Context-free languages are closed under union
b) Context-free languages are closed under concatenation
c) Context-free languages are closed under intersection
d) Context-free languages are closed under Kleene closure
View Answer
Answer: c
Explanation: CFL is closed under Kleene closure, concatenation, and Union

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: Solved MCQs on Finite Automata
Solved MCQs on Finite Automata
COMPUTER SCIENCE SOLVED MCQS
https://cs-mcqs.blogspot.com/2018/04/solved-mcqs-on-finite-automata.html
https://cs-mcqs.blogspot.com/
https://cs-mcqs.blogspot.com/
https://cs-mcqs.blogspot.com/2018/04/solved-mcqs-on-finite-automata.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