# All Questions

660 questions
Filter by
Sorted by
Tagged with
1answer
51 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
495 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
50 views

1answer
38 views

### Formal proof of language accepted by a specific CFG

Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align} Please provide a formal proof for the following ...
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 ...
1answer
34 views

1answer
119 views

### When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule ...
1answer
34 views

### How to find the language and create Push down automaton if the A is continuously looping ? and will PDA accept L produced without A

Let us consider the following Context-Free Grammar G = ({S,A,B,C,D},{a, b}, S, P) with production rules P: S → SSA | Bb A → BSA B → A | Cb C → AD | Cb | ɛ D → a | b | ɛ Let L be the language ...
2answers
53 views

### PDA with more than one initial state

I'm wondering if PDAs with more than one initial states are also accepting context free languages. If found that question on this site about NFAs and would like to know if this answer is also valid ...