Linked Questions

-1
votes
1answer
44 views

Find the language from a context free grammar

I am having trouble determining the language from a given context free grammar. I've been given a hint that there are 2 parts to the language but can't figure either out. $$G= (\{S,A,B,C,D,E,Z\},(0,...
2
votes
2answers
152 views

Proof for BFS and DFS equivalence

I'm trying to prove (by induction) that BFS in equivalent to DFS, in the sense that they return the same set of visited nodes, but I'm stuck in the middle of some of the cases. Let $G$ be a directed ...
2
votes
1answer
83 views

How to produce a context free grammar for this language?

I've already attempted it but I am finding it difficult to understand if this is correct. give a context free grammar for the following: $$ \{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$$ The answer i've ...
2
votes
0answers
235 views

Context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ [duplicate]

Find a context-sensitive grammar for language $L = \left\{ww \mid w \in \left\{a,b\right\}^* \right\}$ where $L \in DCSL \setminus CFL$. I find this task from old exam but there is no solution. I try ...
2
votes
1answer
75 views

Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL

I'm trying to prove $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL. Define $G = ({S,T}, \Sigma, R, S)$ where $R = S \to 0S0|1S1|0T1|1T0, \; T \to 0T|1T|\varepsilon$. Now I want to show ...
0
votes
2answers
112 views

Removing epsilon transition from the grammar. What's the difference between accepting languages?

I want to remove the epsilon transition from following grammar: \begin{eqnarray} S & \rightarrow & A | B \\ A & \rightarrow & \epsilon \\ B & \rightarrow & aBa \\ B & \...
1
vote
2answers
280 views

Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
0
votes
0answers
86 views

Does this grammar generate regular language?

$S \rightarrow AB$ $A \rightarrow aA \mid bA \mid \epsilon$ $B \rightarrow aBb \mid \epsilon$ Does this grammar generate regular language? According to me this grammar generates language of the ...
0
votes
2answers
325 views

Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof

Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. ...
1
vote
1answer
268 views

Determining Language from Context Free Grammar

I am trying to understand how to write the language given the predicates of the context free grammar. As an example, I have the following grammar: $S \to 0B \mid 1A$ $A \to 0 \mid 0S \mid 1AA$ $B \...
0
votes
0answers
45 views

Is this language equivalent to this grammar?

The book that I'm reading says it is equivalent But what about the aa string ? i produce it this way : $$ S\Rightarrow S_1B\Rightarrow aS_1bB\Rightarrow aaB\Rightarrow aa $$ But that language doesn'...
2
votes
1answer
2k views

Is the language of all non-palindromes context-free?

Is the language $L = \{ w \mid w \in (a,b)^* \wedge w \text{ is not a palindrome} \}$, context-free? I think this grammar: $ S \rightarrow aSa \mid bSb \mid aAb \mid bAa\\ A \rightarrow aAa \mid bAb \...
0
votes
1answer
1k views

PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
-2
votes
1answer
118 views

$L = \{ w \in \{0, 1, 2\}^*: |0| + |2| = |1| \}$ where |0| denotes number of 0s in the string w

I have come up with: S→0SX | 1SY | 2SZ | SS | ϵ X→1 Y→0 | 2 Z→1 I think I am wrong. Any directions?
1
vote
1answer
98 views

Language of CFG: $S \to aS | aSbS | \varepsilon$

I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I ...

15 30 50 per page