MyQuestionIcon

1

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

Regular Grammars Part - 2

Consider the ...

Question

Consider the following grammar G
$S \to b S | a A | b$
$A \to b A | a B$
$B \to b B | a S | a$
Let $N_{a} (w) a n d$ $N_{b} (w)$ denote the number of a's and b's in a string w respectively. The language L(G) $\subseteq$ {a,b} $^{+}$ generated by G is

Open in App

Solution

Draw the fa of the given grammar as shown below:

Clearly, the machine is accepting $N_{a} (w) = 3 k,$ where k $ϵ$ {0,1,2,3,...}

Suggest Corrections

thumbs-up

0

Similar questions

Q. Consider the following context-free grammars:

G_{1} : S \to a S | B, B \to b | b B

G_{2} : S \to a A | b B, A \to a A | B | ε, B \to b B | ε

W h i c h o n e o f t h e f o l l o w i n g p a i r s o f l a n g u a g e s i s g e n e r a t e d b y G_{1} a n d G_{2}, r e s p e c t i v e l y ?

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. 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. 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. Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules

$S \to b A$	$S \to a B$
$A \to a$	$B \to b$
$A \to a S$	$B \to b S$
$A \to b A A$	$B \to a B B$

Which of the following string is generated by the grammar?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Regular Grammars Part - 2

OTHER

Watch in App

explore_more_icon

Explore more

Regular Grammars Part - 2

Join BYJU'S Learning Program

CrossIcon