# All Questions

670 questions
Filter by
Sorted by
Tagged with
0answers
39 views

### Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$

I have written a CFG that supposedly generates $L$ below. $$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$ Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...
2answers
116 views

### Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?
4answers
78 views

### Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

I'm trying to prove that the following languague is a regular language: $L=\{ w \mid \lvert w \rvert$ is prime $\}$* What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
1answer
32 views

2answers
468 views

### Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
1answer
31 views

### Grammar for $\{ a^i b^j: j < 2i \text{ and } j \ne i \}$

For the following language, write grammar independent of the text. $$\{a^i b^j: j < 2i \text{ and } j \ne i \}$$ I want a hint to start solving this problem. Where should I start?
0answers
19 views

### Is my context free grammar of this language right?

L = { a^m b^n a^o a^p b^q : m >= n, o >= p + q } That's what I tried to do: S -> aSb|bSa|A A -> aA|ε Is my CFG right? I'm missing something? My difficult it's in this part o >= p + q
3answers
219 views

### Need help understanding what co-recursively enumerable means

Lets say I have a set: $L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
1answer
54 views

### Is this language a context free language?

Consider the following language, where the alphabet is $\{0, 1, 2\}$: $B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$. Is this language a context free language? Prove your answer. I am ...
2answers
585 views

### Given L is a regular language, prove that Perm(L) is Context-Free

Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\},$$ where $perm(x)$ is the set of all permutations of the ...
1answer
53 views

0answers
14 views

### Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
0answers
128 views

### is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
1answer
326 views

### Undecidability of “is this CFG prefix-free?”

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition). Another thread has the very different question "...