1
$\begingroup$

I am new to CFG's, Can someone give me tips in creating CFG that generates some language

For example

$L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where $w^R$ is the reverse of string $w$.

I'm having trouble understanding the language .. I want to build DFA to convert it

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Welcome to SE Computer Science. What is your idea of the language, even if you have trouble understanding it? What can a DFA have to do with your problem? $\endgroup$
    – babou
    Commented May 27, 2015 at 18:08
  • $\begingroup$ I would build a DFA to convert it to CFG .. but the language not clear fo me $\endgroup$
    – Abdallha dagga
    Commented May 27, 2015 at 18:13
  • $\begingroup$ use the search engine to find similar questions in this site, and get some intuition. See, for example, this question $\endgroup$
    – Ran G.
    Commented May 27, 2015 at 18:41
  • $\begingroup$ also check our reference questions, and in particular this one $\endgroup$
    – Ran G.
    Commented May 27, 2015 at 18:45
  • 1
    $\begingroup$ I think you are confusing DFA (Deterministic Finite Automaton) with PDA (Push-Down Automaton) $\endgroup$
    – babou
    Commented May 27, 2015 at 18:48

2 Answers 2

Reset to default
3
$\begingroup$

Mmmm.

Let me note that in fact $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$ equals $\{ v \mid v \in \{a,b\}^*\wedge|v| \text{ is even } \}$.

Al strings in $L$ are of even length, and conversely all strings of even length can be otained by taking $w=\varepsilon$.

That should help.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I wonder whether this was expected ! $\endgroup$
    – babou
    Commented May 27, 2015 at 23:43
  • $\begingroup$ @babou That is a good question. Perhaps the DFA confusion is related to this? $\endgroup$
    – Hendrik Jan
    Commented May 28, 2015 at 0:20
  • 2
    $\begingroup$ Cute! It might help the OP even more if you included a sentence of explanation. (Too bad I can't upvote twice.) $\endgroup$
    – Rick Decker
    Commented May 28, 2015 at 1:12
  • $\begingroup$ It is really a great psychological example of the way we work, and what may block us. Science is largely a question of looking at thing the right way. Hence the importance of conceptualization and notation. But in such a simple example ... Great for teaching. $\endgroup$
    – babou
    Commented May 28, 2015 at 8:40
  • $\begingroup$ I think this question should not be closed. The answer is indeed too cute. What do you think? cc @RickDecker $\endgroup$
    – babou
    Commented May 28, 2015 at 13:59
2
$\begingroup$

Hints:

  1. Construct a non-terminal $V$ and appropriate productions so that $V$ generates all strings of even length.

  2. Create productions so that your starting symbol $S$ generates $wVw^R$ for all $w$. To accomplish that, modify a grammar for $ww^R$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.