MyQuestionIcon

1

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Regular Grammars Part - 1

Let L denotes...

Question

Let L denotes the language generated by the grammar $S \to 0 S 0 ∣ 00 W h i c h o f t h e f o l l o w i n g i s t r u e ?$

A

L is regular but not

0^{+}

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

B

L is context free but not regular

No worries! We‘ve got your back. Try BYJU‘S free classes today!

C

L is not context free

No worries! We‘ve got your back. Try BYJU‘S free classes today!

D

L = 0^{+}

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is A L is regular but not $0^{+}$
The language generated by the grammar
$S \to 0 S 0 ∣ 00 i s$
L = ${0^{2}, 0^{4}, 0^{6}, 0^{8}, . . .}$
= ${0^{2 n + 2} ∣ n \geq 0}$
= ${0^{2 n} ∣ n \geq 1} = 00 (00)^{*}$
So above language is regular but not $0^{+} .$

Suggest Corrections

thumbs-up

0

Similar questions

L e t L b e t h e l a n g u a g e o f a l l s t r i n g s o n (0, 1] e n d i n g w i t h 1 . L e t X b e t h e l a n g u a g e g e n e r a t e d b y t h e f o l l o w i n g g r a m m a r G . S \to o S 1 A A \to 1 S o A T h e n L \cup X = ?

Q. Consider an ambiguous grammar G and its disambiguated version D.Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively.Which one of the following is true?

Q. Consider the following problems L(G) denotes the language generated by a grammar G.L(M) denotes the language accepted by a machine M.
I. For an unrestricted grammar G and a string w, whether w

ϵ

L(G).
II. Given a Turing Machine M, whether L(M) is regular.
III. Given two grammars

G_{1} a n d G_{2},

(G_{1}) = L (G_{2})

.
IV. Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.
Which one of the following statements is correct?

Q. In the context-free grammar below, S is the start symbol, a and b are terminals, and

ϵ

denotes the empty strings

S \to

ϵ

A \to

ϵ

The grammar generates the language

Q. Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w,is

ω ε

L(R)?
II. Given a context-free grammar G, is L(G)=

ϕ

III. Given a context-free grammar G, is L(G) =

\sum^{*}

for some alphabet

\sum

?
IV. Given a Turing machine M and a string

ω

ω ε

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Regular Grammars Part - 1

OTHER

Watch in App

explore_more_icon

Explore more

Regular Grammars Part - 1

Join BYJU'S Learning Program

CrossIcon