Register

GO Classes CS Test Series | Mock GATE | Test 4 | Question: 14

• retagged by
767 views
6 6 votes

$$
\text{S} \rightarrow a \text{S} b \mid b \text{S} a \mid \text{SS} \mid \epsilon
$$
Which of the following best characterizes the language generated by the grammar above?

  1. All strings of the form $a^i b^j a^k,$ where $i+j=k$
  2. All palindromes over $a$ and $b$
  3. All strings with equal numbers of $a\text{'s}$ and $b\text{'s}$ 
  4. All strings of the form $w w^\text{R},$ where $w \epsilon\{a, b\}^*$

1 Answer

5 5 votes
Given grammar generates $abab,$ so, options A, B, D are wrong. Option C is correct.

The given grammar is a standard grammar for the language where the number of $a’s$ is same as the number of $b’s.$
• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes CS Test S...Next → · GO Classes CS Test S...
← Previous in category · GO Classes CS Test S...Next in category → · GO Classes CS Test S...
Position:
Show:

Related questions

35 35 votes
5 5 answers
3.8k
3.8k views
GO Classes asked Jan 19, 2023
3,815 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 12
Let $\text{L}$ be a language consisting of finitely many strings. Hence, $\text{L}$ is regular and, therefore, context-free.Let $k$ be the maximum length of any string in...
28 28 votes
4 4 answers
3.0k
3.0k views
GO Classes asked Jan 19, 2023
3,042 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 13
For any language $\text{L},$ we define two operations, square and double as follows:The square of a language $\mathrm{L}$ is $\mathrm{Sq}(\mathrm{L})=\{ww: w \in \mathrm{...
19 19 votes
2 2 answers
2.6k
2.6k views
GO Classes asked Jan 19, 2023
2,564 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 37
Which of the following decision problems is decidable$? \;\text{(TM}$ stands for Turing Machine)Given a $\text{TM M}$ and a string $w,$ does $\text{M}$ ever write the sym...
26 26 votes
2 2 answers
2.8k
2.8k views
GO Classes asked Jan 19, 2023
2,784 views
GO Classes CS Test Series | Mock GATE | Test 4 | Question: 65
If $\mathrm{A}$ is a set, let $|\mathrm{A}|$ denote the cardinality of set $\mathrm{A}$.We say $\text{|B|}=|\text{A}|$ if and only if there exists a bijection from $\text...