Testbook Logo
Exams SuperCoaching Test Series Skill Academy
More
English
Hindi

Question

Download Solution PDF

Which of the following is strictly more powerful than regular expression?

This question was previously asked in
LMRC Assistant Manager IT/CS: 2018 Official Paper
Download PDF Attempt Online
View all LMRC AM Papers >
  1. Nondeterministic Finite Automation (NFA)
  2. Context-free grammar
  3. DFA
  4. Recursive function

Answer (Detailed Solution Below)

Option 2 : Context-free grammar

Detailed Solution

Download Solution PDF

Concept:

Context free grammar is more powerful than regular expression.

Language Power Order: Finite automata DFA ≡ NFA ≡ ϵ -NFA < Push down automata (NPDA > DPDA) < Linear Bound automata < Turing machine (DTM ≡ NTM)

Explanation:

Any language that can be generated using regular expressions can be generated by a context free grammar but there are languages that can be generated by a context free grammar that cannot be generated by any regular expression.

Hence option 2 is the correct answer.

Note:

NFA → Nondeterministic Finite Automation

DFA → Deterministic Finite Automation

DPDA → Deterministic Push down automata

NPDA → Nondeterministic Push down automata

DTM → Deterministic Turing Machine

DTM → Nondeterministic Turing Machine

Download Solution PDF
Latest LMRC AM Updates

Last updated on Jun 9, 2024

-> UPMRC Assistant Manager Result has been released.

-> The exam was conducted on 11th, 12th, and 14th May 2024. The provisionally selected candidates will be called for DV and Medical examination.

-> Eligible candidates had applied online from 20th March to 19th April 2024.

-> A total of 31 vacancies have been announced.

-> Eligible candidates can apply online from 20th March to 19th April 2024.

-> The UPMRC Assistant Manager Selection Process consists of three stages - computer-Based Test, Document verification, and a Medical examination.

-> The salary of the finally appointed candidates will be in the pay scale of Rs. 50,000 to Rs. 1,60,000.

More Context Free Grammars Questions

Q1.Let L = L1 ∩ L2 where L1 and L2 are language defined below : L1 = {ambmc an bn m, n ≥ 0} L2 = {aibj ck | i, j, k ≥ 0} Then L is : 
Q2.Let A= {a, b} and L = A*. Let x = {anbn, n > 0}. The languages L ∪ X and X are respectively :  
Q3.The maximum yield length of the following CNF CFG is S → AB A → CD B → e C → a D → b
Q4.Which of the following statement is correct? 
Q5.Match the following based on the language accepted by using brute force method of parsing. LIST - I LIST - II A. S → aSa | aa I. ((2n * 3) - 4) ; n ≥ 1 B. S → aaSaa | aa II. 2n ; n ≥ 1 C. S → aaaSaaa | aa III. ((4 * 2n) - 6) ; n ≥ 1 D. S → aaaaSaaaa | aa IV. 2n - 2 ; n ≥ 2 Choose the correct answer from the options given below: 
Q6.Match List I with List II: List I List II (A) Type 0 (I) Finite automata (B) Type 1 (II) Tuning machine (C) Type 2 (III) Linear bound automata (D) Type 3 (IV) Pushdown automata Choose the correct answer from the options given below:
Q7.The reduced grammar equivalent to the grammar, whose production rules are given below, is S → AB | CA B → BC | AB A → a C → a B | b
Q8.Select the sentence which is meaningful and grammatically correct.
Q9.Match List I with List II List I List II Production Rules Grammar A. S → XY X → 0 Y → 1 I. Greibach Normal Form B. S → aS| bSS |c II. Context Sensitive Grammar C. S → AB A → 0A | 1A | 0 B → 0A III.  Chomsky Normal Form D. S → aAbc Ab → bA Ac → Bbcc bB → Bb aB → aa | aaA IV. S-Grammar Choose the correct answer from the options given below :
Q10.Any string of terminals that can be generated by the following context free grammar (where S is start nonterminal symbol) S → XY X → 0X | 1X | 0 Y → Y0 | Y1 | 0

More Context Free Languages and Pushdown Automata Questions

Q1.Let L = L1 ∩ L2 where L1 and L2 are language defined below : L1 = {ambmc an bn m, n ≥ 0} L2 = {aibj ck | i, j, k ≥ 0} Then L is : 
Q2.Consider the grammar with nonterminals N = {S, C, S1} terminals T = {a, b, i, t, e} With S as the start symbol , and the following set of rules : S → i Ct SS1|a S1 → es | ∈ C → b The grammar is not LL(1) because : 
Q3.Which of the following represents the output of the transition function(δ) δ(q0,a) = (q1, x, R) δ(q1,a) = (q1, a, R) δ(q1, y) = (q1, y, R) δ(q1, b) = (q2, y, L) δ(q2, y) = (q2, y, L) δ(q2, a) = (q2, a, L) δ(q2, x) = (q0, x, R) δ(q0, y) = (q3, y, R) δ(q3, y) = (q3, y, R) δ(q3, ◻) = (qf, ◻, R)
Q4.Choose the correct statement(s) A. A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time. B. All NP-complete problem are NP-hard problems. C. If an NP-hard problem can be solved in polynomial time, then all NP-complete problem can be solved in polynomial time D. All NP-hard-problems are not NP-complete. Choose the correct answer from the options given below:
Q5.Let A= {a, b} and L = A*. Let x = {anbn, n > 0}. The languages L ∪ X and X are respectively :  
Q6.Consider following statements: A. A context free language is generated by LR(o) grammar if and only if it is accepted by a deterministic pushdown automata and has prefix property B. If M1 is the single tape TM simulating multilape TM M, then time taken by M1 to simulate n moves is (n3) C. Push down automata behaves like a Turning machine when it has one auxiliary memory. D. L= {anbncn : n ≥ 1} is not context free but context sensitive. Choose the correct answer from the options given below:
Q7.The maximum yield length of the following CNF CFG is S → AB A → CD B → e C → a D → b
Q8.Which of the following statement is correct? 
Q9.What is the safest order while simplifying Context Free Grammar?
Q10.Match the following based on the language accepted by using brute force method of parsing. LIST - I LIST - II A. S → aSa | aa I. ((2n * 3) - 4) ; n ≥ 1 B. S → aaSaa | aa II. 2n ; n ≥ 1 C. S → aaaSaaa | aa III. ((4 * 2n) - 6) ; n ≥ 1 D. S → aaaaSaaaa | aa IV. 2n - 2 ; n ≥ 2 Choose the correct answer from the options given below: 
Crack AE & JE - Civil with
India's Super Teachers
Explore Supercoaching For FREE
Suggested Test Series
View All >
AE & JE Civil Engg. Exams Previous Year Papers Mock Test
469 Total Tests with 8 Free Tests
Start Free Test
AE & JE Electrical Engg. Exams Previous Year Papers Mock Test
276 Total Tests with   9 Free Tests
Start Free Test
Suggested Exams
Exam-Logo
UPRVUNL JE
Exam-Logo
LMRC AM
Exam-Logo
GATE CS

UPRVUNL JE Important Links

More Theory of Computation Questions

Q1.Consider the finite automata given below : The language b accepted by this automata is given by the regular expression :
Q2.Let L = L1 ∩ L2 where L1 and L2 are language defined below : L1 = {ambmc an bn m, n ≥ 0} L2 = {aibj ck | i, j, k ≥ 0} Then L is : 
Q3.If T1 and T2 are two Turing machines. The composite can be represented using the expression :
Q4.__________ is the most general phase structured grammar.
Q5.Consider the grammar with nonterminals N = {S, C, S1} terminals T = {a, b, i, t, e} With S as the start symbol , and the following set of rules : S → i Ct SS1|a S1 → es | ∈ C → b The grammar is not LL(1) because : 
Q6.Which of the following problems is undecidable ? 
Q7.Which of the following represented the minimum state DFA for the above specified passage?
Q8.For the above specified passage, which of the following represent the grammar for the language accepted the machine?
Q9.For the above mentioned passage which of the following is correct?
Q10.For the above specified passage, which of the following represents the regular expression?
Important Exams
Super Coaching
Exams
Test Series
Previous Year Papers
Books
Objective Questions
Testbook Products & Resources for Students
Testbook USA
Testbook Edu Solutions Pvt. Ltd.
1st & 2nd Floor, Zion Building,
Plot No. 273, Sector 10, Kharghar,
Navi Mumbai - 410210
[email protected]
Toll Free:1800 833 0800
Office Hours: 10 AM to 7 PM (all 7 days)
Company
About usCareers We are hiringTeach Online on TestbookPartnersMediaSitemap
Products
Test SeriesTestbook PassOnline CoursesOnline VideosPracticeBlogRefer & EarnBooks
Our Apps
Follow us on
Copyright © 2014-2022 Testbook Edu Solutions Pvt. Ltd.: All rights reserved
User PolicyTermsPrivacy
Get Free Access Now
Hot Links： teen patti - 3patti cards game downloadable content teen patti master apk download teen patti win teen patti royal - 3 patti