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
161 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
84 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
327 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 ...
-1
votes
1answer
2k views

Describing language generated by grammar

S -> aSb | A | B A -> aS | a B -> Sb | b is this the language generated by this CFG? Or am I missing something?
0
votes
0answers
35 views

Context Free Grammar for a language [duplicate]

I have a language L = {a^n b^m c^k | n = m or m != k} When I was working the problem out this is what I got: S -> S1|S2 S1 -> AC A -> aAb|$\lambda$ C -> Cc |$\lambda$ S2 -> BD B -> aB|$\lambda$ D ->...
2
votes
1answer
269 views

Prove the equivalence between a CFG and a Context free language

I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules: $S\rightarrow a^2Tb$ $T\rightarrow a^3Tb^2 |\epsilon$ are equivalent to each other. I'm ...
1
vote
0answers
117 views

Regular Expression for All strings which contain no runs of a's of length greater than two.On L={a,b,c} [closed]

My attempt is We can fairly easily build an expression containing no a, one a, or one aa: (b+c)(€+a+aa)(b+c) but if we want to repeat this, we need to be sure to have at least one non-a between ...
1
vote
1answer
202 views

Prove L = L(R) based on a regular expression

I'm given the following language: L = {w∈{0,1}* | w ends in 010 and contains 011} The task is to find a regular expression R that describes this language and ...
4
votes
1answer
393 views

Finding the language of a context-free grammar?

Given following question: Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $...
0
votes
2answers
466 views

Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
0
votes
2answers
570 views

Finding Language of a CFG

Say you are given the following CFG $G$: $$ S \to S_1 \mid S_2 \\ S_1 \to AbAS_1c \mid \epsilon \\ S_2 \to BaBS_2c \mid \epsilon \\ A \to Aa \mid \epsilon \\ B \to Bb \mid \epsilon $$ What is $L(G)$? ...
1
vote
1answer
83 views

Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$?

At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the ...
2
votes
1answer
562 views

Show that language generated by grammar is regular

We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form: $X_i \rightarrow a \in V_t $ $X_i \rightarrow X_jX_k, \ i \ge j , \ i > k $ How can I show that ...
1
vote
2answers
157 views

Show that a language cannot be generated by linear grammar

I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$ that is a language with even number of b's. I found a grammar for it with these rules: $S \rightarrow aS \ | \ bL \ | \ \lambda $...
-2
votes
1answer
75 views

Finding the language generated for CFG

What language generated by the following context-free grammar 1) S------> SaS | b i already know the answer to question one but to prove it would is be something like this: S -----> SaaS -----> baab ...
0
votes
0answers
87 views

Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
-1
votes
2answers
74 views

Design a grammar for this context-free language

I am doing an exercise from Models Of Computation - Ch - 5, Q-1(r). Design a grammar that generates this context-free language $\{ x\space\$\space y^R \,|\, x, y \in\{0, 1\}^* \text{ and } x \ne y\}...
2
votes
1answer
91 views

How do I get and/or verify a formal Grammar for a given formal Language? [duplicate]

I was given the Language $L=\left \{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \}$ and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I ...

15 30 50 per page