MyQuestionIcon

1

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

Union of Sets

Let L be the ...

Question

$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 = ?$

Open in App

Solution

$M a c h i n e o f X; L X = N o t e n d i n g w i t h 1 L \cup X = E n d i n g w i t h 1 \cup n o t e n d i n g w i t h 1 = \sum *$

Suggest Corrections

thumbs-up

0

Similar questions

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

ω

ω ε

Q. 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 ?

Q. Consider a CFG with the following productions.

S \to A A | B

A \to 0 A | A 0 | 1

B \to 0 B 00 | 1

S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is

C o n s i d e r t h e D F A X g i v e n a b o v e o v e r \sum = 0, 1 . L e t L (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 a b o v e D F A . W e a r e g i v e n f o l l o w i n g s t r i n g s . 1 . a^{32} {(b a)}^{128} 2 . a^{2017} b^{2018} a^{2019} 3 . {(a^{72} b^{14})}^{2} 4 . {(\in)}^{32} H o w m a n y o f t h e a b o v e s t r i n g s b e l o n g t o L (X)____.

Q. Which of the following statements are true?
1. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa.
2. All

ε

-productions can be removed from any context-free grammar by suitable transformations.
3. The language generated by a context-free grammar all of whose productions are of the form X

\to w

\to w Y

(where, w is a string of terminals and Y is a non-terminal), is always regular.
4. The derivations trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees.

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Types of Sets

MATHEMATICS

Watch in App

explore_more_icon

Explore more

Standard VIII Mathematics

Join BYJU'S Learning Program

CrossIcon