# Questions tagged [context-free]

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

1,313 questions
Filter by
Sorted by
Tagged with
16k views

### Context-free grammar for language with unequal numbers of a and b

I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e. $$\{u \in \{a, b\}^* \mid \text{number of occurrences of a and b in u are unequal} \},$$ but ...
11 views

### What's the context-free grammar for { w | 2*(number of a's in w) != 3*(number of b's in w) +2 }? [duplicate]

So I have this language: $$A= \{ w \in \{a,b\}^* \mid 2*\#_a(w) \ne 3*\#b(w) + 2\}$$ I know it's context free, I know how to make a PDA for it, I just can't, for the life of me, figure out how to ...
71 views

### Fitting a regular grammar to strings from a PCFG: how big does it get?

Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$. For finite $n$, it is always possible to find a regular ...
55 views

### How can I efficiently construct a CFG from a language

I am new to CFG's and automata in general and I came across an exercise where I needed to construct a CFG for the language {a^m b^n | n <= m + 3}. So m can be infinitely bigger than n but n can ...
24 views

### If one of the case obeys all rules of Pumping Lemma, can we conclude there is no contradiction?

I am studying Pumping Lemma for Context Free Languages, wherein, I am slightly confused in a question where one of the case doesnt obey all rules but another case does. What's the conclusion? Do we ...
63 views

### Using the pumping theorem to show that this language is not context-free

Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free. I really don't know where to start, ...
356 views

### Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
16 views

### Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

In theory, given that: The LALR parser can be constructed by merging LR(1) states with the same core; If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$; ...
12 views

### Derivation tree and Productions from left most derivation of string

How can one find Derivation tree and Productions of a Grammar from left-most derivation and string used? I was given input string x = abaccacaa , left most derivation lder(x)=(1,2,1,3,4,1,3,5) and two ...
145 views

### Decide if this language is context free

I got this question for homework: Decide if this language is context free or not: $\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$. Intuitively I think it's not context-free ...
34 views

### BNF rule to regular expression

I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression. (With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
1k views

37 views

### Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} ) (sorry for the formatting, see screenshot-link for conventional/clear ...
460 views

128 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 ...
26 views

$$L=\left \{ a^nb^m|n\leq m\leq 2n \right \}$$ Is this even context free? I am asking because by looking at the condition, for an expression that holds:$n< m<2n$ can be written as : $a^nb^nb^c (... 1answer 22 views ### How can I combine 2 PDA's into 1 I need to form PDA for this language: {$a^nb^m|n=m \vee n=2m$} I know the idea of building each one separately but how do I combine them into 1 PDA? LHS: for every 'a' I push 'A' inside stack and for ... 1answer 159 views ### How to determine valid handle for given bottom up parser? I came across following question: Consider the grammar:$E → E + n\text{ | }E × n\text{ | }n$For a sentence n + n × n, the handles in the right-sentential form of the reduction are (... 0answers 44 views ### Is it necessary for a Push down Automaton (PDA) to have a stack? I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed? 1answer 91 views ### CFG-Infinite recursion As you see, the string production process never ends. Can someone explain me if this language is regular or not ?$ S \to Α Β S  A \to S  B \to a B b $1answer 39 views ### CFG that generates$1^*$is decidable I read somewhere that the problem which asks whether or not a$CFGG$generates$1^*$is decidable. The proof goes like this:$1^* \cap G$is context free since it is the intersection of a regular ... 2answers 91 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 27 views ### Is there any property about height of PDA? I'm trying to find a PDA for$L$which modifies the stack height at most one.$L=\{a^ib^i\mid i\geq 0\}$I think there is no such PDA but how can I prove it? My attempt is for a given string, find ... 1answer 47 views ### Help with context free grammar excercise So, I have an exercise in which I have to write a context free grammar for this language: $$L = \{x \in L(a^∗b^∗c^∗) : |x|_a > |x|_c; |x|_b > 0; |x|_c ≥ 0\}$$ meaning every string with any ... 1answer 30 views ### Why is the following grammar not LL(1) Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ... 2answers 26 views ### Is the language of rectangular matrices in MATLAB-style syntax context free? Consider the language$L$of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be ... 1answer 42 views ### Pumping Lemma for CFL -$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} \$
I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language: $$\{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \}$$ I ...