# Tagged Questions

16 views

### Proving that a language having a particular CFG grammar is equivalent to a particular L

I think we need to prove that L(G) is a subset of L and then we need to prove that L is a subset of L(G). For the first part, I think we need to say for any w in L(G) we have an even number of as ...
15 views

### Particular Problem for Context Free Grammars

Consider the context-free-grammar $G$ defined by productions: $$S \rightarrow aS\,|\,Sb\,|\,a\,| b$$ Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring. I ...
22 views

28 views

### Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
69 views

### Showing that 2 languages are context free

I have these 2 languages: $$L_1 = \left\{a^ib^jc^k: k\ge i+j\right\}\\ L_2 = \left\{w_1cw_2 : w_1,w_2\in\{a,b\}^\ast\land |w_1|_a = |w_2|_a\right\}$$ How can I determine that they are context free ...
116 views

### Up-Down Automaton

I've been give this question, about Pushdown Automata. they defined a new Automata, up down automata, as followed- it has all options a regular Automata has, but : and for each: now I need to ...
55 views

### Push down automata for context free grammar

I'm having trouble finding the PDA for this language $L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$ The ...
59 views

### Prove that a PDA with accept states accepts all context-free languages

Or in other words that $\forall L: L \in DCFL => L \in CFL$. First of all, does this statement even require a proof? My idea was to let L be an arbitrary language, such that $L \in DCFL$, this ...
354 views

### The shortest word in context free language

Let $G=(\Sigma,N,R,S)$ be a context-free grammar. For every production rule A --> w, we say that its length is $r$ if $|w|=r$. In addition $n = |N|$, and $k =$ the maximal length of a production rule ...
40 views

### Grammar outside the Chomsky Hierarchy

This grammar describes a language that may fall outside the Chomsky Hierarchy (CH): \begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array} Going ...
33 views

### Consider this grammar

Consider this grammar: \begin{array}{l} S \to aabBba \mid aAb \mid aab \\ bBb \to bCa \mid aaa\\ aA \to aC \mid bba\\ C \to aab \mid Cb \end{array} This is clearly context-sensitive (CS). It's not ...
29 views

### Is this a context-free language?

Let $L = L_1^* \circ L_2^*$ where $L_1 = \{1^n 0^m 1^n : n,m \in \Bbb N\}$ and $L_2 = \{0^m 1^{2m} : m \in N\}$. Is the language $L$ a context free language? I think I can write automata for $L_1$ ...
55 views

120 views

### How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\}$?

How to construct a context free grammar $G$ such that $L(G) = \{ a^i b^j c^k| j \gt i+k\}$? I don't have much idea how to approach this one. Could some help me to understand how to approach these ...
73 views

### Pumping Lemma length, $K$ for context-free language

Please help me understand, and if possible, tips, to determine a pumping length $K$. Suppose I have the example : Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,T\}$, set of ...
182 views

### Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]

How do you show that there exists no DPDA that accepts $L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
61 views

### Constructing PDA with either one state or two states

If $L$ is a context-free language and $\epsilon \notin L$, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
96 views

### Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.

I'm having my exam in few days and I would like help with this Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.
312 views

### Push down automata problem

Informally describe the Nondeterministic PDA that generates: $$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$ My initial plan was to use nondeterminism to go through each character before ...
115 views

### Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
145 views

### Context Free Language? Proving through grammar?

I need help solving this question: Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language? That is the number of $a$'s equal the number of $b$'s equal twice the ...
Prove or disprove Let $L$ be an infinite context free language. Show that there exists a regular language $R$ such that $L \cap R$ and $L \cap \overline{R}$ are infinite and regular.