# Questions tagged [context-free]

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

1,146 questions
Filter by
Sorted by
Tagged with
44 views

### What strategies exist for handling/resolving ambiguity in parsers?

I define a parser as a context-free grammar with semantic actions for each production. It is not defined in what order the semantic actions run, just that the semantic actions of the non-terminals in ...
44 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 ...
21 views

### Given set of grammar rules, how to find if they correspond to Context-free or unrestricted

Given set of grammar rules, how to find if they correspond to Context-free or unrestricted? Just for Understanding (don't solve the below one), eg: \begin{align} S &\rightarrow B/A, \\ 1B &\...
73 views

### How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount

I know that CFG for $$\{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is $$S\rightarrow ab/abb/aSb/aSbb$$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to ...
28 views

### Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}

I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help Thanks in Advance!
73 views

### Leo's deterministic reduction for Earley Parsing

I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows: ...
19 views

### Is the set of context free grammars that generate no words in co-RE? [duplicate]

Is the $\{ \langle G \rangle \mid L(G) = \emptyset \}$ recursively enumerable or co-recursively enumerable?
28 views

### Efficiency/Redundancy in Chomsky normal form

I have a context-free grammar with the following production rules, $S$ being the start symbol: \begin{align*} S &\to AB \\ A &\to a \\ B &\to a\end{align*} Is this in Chomsky normal ...
47 views

### What is an example of a decidable language?

I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
80 views

### How to give a context free grammar for any given language ie: a^n (ba)^m a^n

i am trying to understand Context free grammar and generate a CFG for any given language. when you're given a language , what is the best way to generate a CFG from it? are there any steps to follow ...
123 views

### Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$ So far, this is the solution that I have been able to come up with, though I am not sure how accurate ...
52 views

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

Lets say I have a set: $L = \{\langle G \rangle | L(G) = \sum^{\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 ...
41 views

### Is the set of context free grammars that generate all words in co-RE?

Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.
28 views

### Is $L = a^{n}b^{n+m}c^{m} | n,m \geq 0$ a context free or a recursive language?

My initial thought is that L can't be context free since I can use the pumping lemma. I also don't think a grammar can be generated since it needs to keep track of the number of c's and a's. However, ...
31 views

### Given a CFL L and a regular language R, is $\overline{L} \cap R = \emptyset$ decidable or undecidable? [duplicate]

I think it is undecidable since context free languages are not closed under complementation. But I'm stuck because if $\overline{L}$ is regular than $R \cap R = \emptyset$ is decidable since every ...
52 views

### if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

I am having a hard time understanding if this would be true or false, can someone point me in the right direction?
195 views

### Does every infinite context free language contain an infinite regular subset?

Can someone explain to me if this is true or not?
58 views

### Is $\{ 0^p1^q0^r \mid p \neq r \}$ context-free?

Consider the following languages: \begin{align*} L_1 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0 \}, \\ L_2 &= \{ 0^p 1^q 0^r \mid p,q,r \ge 0, \; p \neq r \}. \end{align*} Which one of ...
313 views

### Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
44 views

### Building deterministic pushdown automaton for given grammar

I am trying to build a DPDA for the given grammar: $S \to aR$ $R \to bRT \ |\ \varepsilon$ $T \to cSR \ |\ \varepsilon$ I tried simplifying grammar first (removing null and unit productions, ...
115 views

### How prefix property of language affects the PDA

I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this ...
262 views

### Prove complement a^nb^nc^n is contextfree

So the complement of L1 = {$a^{n}b^{n}c^{n}$ | n $\geq$ 1} would be L2 = {a,b,c}* \ {$a^{n}b^{n}c^{n}$ | n $\geq$ 1}. In other words, any combinations of a,b and c where we dont have an equal number ...
58 views

### Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]

Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
### contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2} [duplicate]
Is this language contextfree? {w1w2 | w1,w2 $\in$ {a,b}* $\land$ |w1| = |w2| $\land$ w1 $\neq$ w2}. I think it's not but can't prove it.