# Questions tagged [context-free]

Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

1,258 questions
Filter by
Sorted by
Tagged with
3 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 ...
17 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 ...
12 views

34 views

### What is context free grammer of $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$

I can't find out how to find a context free grammar for bellow language, is there any specific way to solve that? $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$
27 views

### context free grammar of given language

I wonder how can I find out what is context-free grammar of the following language? $$L_4 = \{w_1\#w_2 \mid w_1,w_2 \in \Sigma^*, w_1 \neq w_2^R \}$$
64 views

### Context free grammar for $A \circ B$

If A and B are regular language, what is a context free grammar of the following language? $$A \circ B = \{ xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y| \}$$
25 views

### Making context-free grammar unambiguous

I'm trying to change below context free grammar such that it becomes unambiguous, but I don't know what steps I should take. Is there any specific way of doing that? Here is my CFG: \begin{align} &...
39 views

### Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$

I try to find a context free grammar for the language $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint ...
36 views

### what is CFG of $\{a^i b^j c^k \mid k = |i-j| \}$

what steps should I take to find out what is the context free grammar of $L(w) = \{a^i b^j c^k \mid k = |i-j| \}$
24 views

### Context free Grammar for x1#x2#…#xn

Design a Context-free grammar (CFG) for this language
60 views

### Is the following language is a context free grammar language?

The question is to determine whether L is a context free grammar language, what do you think?
41 views

### generate CFG from words that have even length and have at most two 0's

How to I generate a CFG from the language that have even length and have at most two 0’s L3 = {w ∈ {0, 1} ∗ | w is even length, 0<=2 } I feel stuck on meeting the criteria of maximum two 0s My ...
28 views

### How to show that Language is not Context Free?

There is a question to show that $L=\{a^{n!} \mid n \geq 0 \}$ is not regular using Pumping Lemma. However, I have the answer in the book which is found to be somewhere wrong. I am sharing the ...
79 views

### Unambiguous context-free grammar for strings with at least as many a's as b's

I have designed this Grammar but it is ambiguous: $$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$ Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
40 views

### Given a CFG and one of its nonterminals $v$ determine if there exists a sentential form beginning with $v$?

I am supposed to find an algorithm solving the following problem: Given a CFG $\;G=(V_N, V_T, R, S)$ and a nonterminal $v \in V_N$ determine if there exists a sentential form which begins with $v$. ...
32 views

### PDA for parentheses language

Construct a PDA for the language described by the following CFG: $$S \to [S] \mid \{S\} \mid \Lambda$$ How can I develop a pushdown automaton for this language?
18 views

### Language of particular CFG

Let: $G = <V, \Sigma, R, S >: \\ V = \{ S,A,B,C \} \\ \Sigma = \{0, 1\} \\ R: \\ S \to CSC|A \\ A \to 0B1|1B0 \\ B \to CB|\epsilon\\ C \to 1|0$ I need to find the language (no need to ...
21 views

### CFG for language of words with odd many $a$ and exactly two $c$

I am trying to construct a context-free grammar for the language $$L = \{ w \in \{a,b,c\} \mid w \text{ contains an odd amount of } a \text{ and there are exactly two } c \}.$$ I am currently stuck ...
41 views

### What does “Every CFL is decidable” exactly mean?

I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means. I know that generation of a particular string by a given CFG is a ...
37 views

### Use or Importance of $\Rightarrow^*$ operator

Particularly, there are 2 variants of $\Rightarrow$, one is $\Rightarrow^*$ and another is $\Rightarrow^+$ which are used in derivation of strings using the productions of the grammar. As stated here,...
36 views

### Is the language of palindromes context-free?

Is the language $\{ w=w^R \mid w \in \{0,1\}^* \}$ a context-free language? I am confused in deciding whether the language is context-free or not, that is one of my problems, I do a pumping lemma ...
19 views

### How do I calculate the probability of a PCFG rule in a parser?

I'm quite struggling with calculating the probability of a rule for a PCFG. I've been looking for examples online and more information, but I am none the wiser. Here is an image of the slides. I ...
35 views

### How do I convert this PDA to CFG?

How do I convert this PDA to CFG? I am currently stuck with this, any help would be appreciated, thank you in advance!
31 views

### The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani, where I came across few statements ...
19 views

### Grammar for $\{a^n b^m c^{n+m} \mid n,m \ge 1\}$ [duplicate]

Please help me solve this problem: Design a grammar for the language $\{ a^n b^m c^{n+m} \mid n,m\ge 1\}$.
38 views

### CFG for this language $\{a^k b^m c^n \mid 1 \leq k, m, n, n \leq 2k\}$ [duplicate]

I'm kinda new in this topic and I don't know how to figure out the rules to make a CFG out of this language, if anyone could give me an idea or hint so I can try to solve it knowing that, I would be ...
102 views

### Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?

I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating ...
24 views

### A grammar for my context free language {xy | x, y ∈ {a, b} ∗ , |x| =|y| , x != y}

This question is given as an exercise to me . I took a look at the solution given by the instructor which is not the same as my solution . So I thought it would be wise to ask it here considering ...
30 views

21 views

### Unambiguous grammars with different right and left hand derivations

I read recently that for an unambiguous grammar the left hand derivation need not necessarily be equal to the right hand derivation. Can someone give an example of this?
28 views

### Is there a pda with maximum 3 state for every CFL?

This is the first question I'm asking here I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?
15 views

### How can I create the context free grammar for this language? [duplicate]

I need help finding the context-free grammar for this language. $$L = \{a^ib^jc^k \in \{a,b,c\}^* \mid \text{i,j,k \geq 1, and i=j or i=k or both}\}.$$ I've found a way to satisfy $i = j$ ...
31 views

### how to write a language for context-free grammar generates the empty string?

How would you write a language for a context-free grammar that generates an empty string. Is it something like E = { (G) | G is a CFG and L(G) = Ø}?
36 views

This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3. $$\text {Let }b_i \text{ denote } i \text{... 1answer 29 views ### What is the language generated by this grammar? I'm struggling to find the language generated by the following grammar: Any help would be appreciated. 1answer 23 views ### Context-free grammar for language involving multiplication I'm struggling to find the context-free grammar for the following language:$$ L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\} $$Any help would be appreciated. 1answer 24 views ### Find CFG for the following language I need to show that the following language is context free:$$L = \{a^\ell b^n c^m | \ell, n, m \in \mathbb{N}^+ \wedge ((\ell \ge n) \vee (\ell \ge m))\}$$0answers 26 views ### Context free grammar Help I need to create a CFG for the following language:$$ \{a^ib^jc^k|i≤j≤2i, k=2j\}  Getting the a's and c's to be correct is easy enough but everything else is confusing me slightly. any help would ...
I recently learned about the conversion, but I seem to be stuck. I need to convert the following CFG to CNF: $S → XY$ $X → abb|aXb|e$ $Y → c|cY$ There is no S on the right side, so I did not need ...