edited by
3,679 views
23 votes
23 votes

In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string

$S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon$

Which of the following strings is NOT generated by the grammar?

  1. $aaaa$
  2. $baba$
  3. $abba$
  4. $babaaabab$
edited by

3 Answers

Best answer
34 votes
34 votes

$L(G) = PALINDROME  $

$baba$  does not belong to palindrome , so B is the answer.

edited by
0 votes
0 votes
S → aSa | bSb | a | b | ϵ
Given string accepts all palindromes.
Option B → baba is not palindrome.
So, this is not accepted by S.
0 votes
0 votes

Grammar is generating strings like

 

L = {$(ab)^{n}.(ba)^{n}$ | $(ba)^{n}.(ab)^{n}$ | $(a)^{n}.(a)^{n}$ | $(b)^{n}.(b)^{n}$ } 

so $baba$ is not accepted.

B

Answer:

Related questions

38 votes
38 votes
6 answers
2
Ishrat Jahan asked Oct 31, 2014
9,717 views
Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ isalways regularnever regularalways a deterministic context-free languagealways...
29 votes
29 votes
1 answer
3
Ishrat Jahan asked Oct 31, 2014
7,881 views
Which of the following statements about regular languages is NOT true ?Every language has a regular supersetEvery language has a regular subsetEvery subset of a regular l...