# Questions tagged [context-free]

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

1,197 questions
Filter by
Sorted by
Tagged with
159 views

### If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language? [closed]

If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free? I am aware that if $L_1$ and $L_2$ are context free languages then the ...
122 views

### Complement DCFGs and handles

If I have a DCFG G for some language over {0,1}* and a DCFG H for its complement, with disjoint non-terminals, and a (perhaps partially reduced) string, can they both have a handle for the string? So ...
5k views

### Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
150 views

### Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
287 views

### Context-free grammar for $L = \{a^n : n\leq2^{20}\}$

I want to find a context-free grammar for $L = \{a^n : n\leq2^{20}\}$. There's one for sure. I approached it by two ways and both seemed dead end. One was to set a limit during the production of the ...
3k views

### Simplification of CFG

Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft. The grammar goes as follows S-> aAa | aBC A -> aS | bD B - > aBa | b C-> abb | DD D -> aDa In the ...
66 views

### What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
469 views

### CFL not closed under intersection while Turing Decidable are

It makes me wonder that despite of (CFL) being a subset of Turing Decidable languages, Turing Decidable is closed under intersection while CFL is not. Does not Turing Decidable engulf all CFLs?
406 views

### Complexity of CFG grammar for a regular language

I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages. Are there known results about the '...
2k views

### Context-free language and regular expressions

I have the following context-free language: S -> ASa | b A -> aA | a I don't understand why this is not regular. I first said that it's generated by the ...
282 views

### What Do Logical Operators In a Grammar Mean?

Is there a way to figure out what the following CFG accepts? \qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid\; \thicksim p \end{align} I'...
3k views

### Determining if a context-free grammar produces even-length strings [closed]

Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?
517 views

### How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
75 views

### Why CFG can specify structure of sentence but Regular grammar cannot? [duplicate]

CFG can specify structure of sentences but Regular grammar can only specify strings sequentially. Is it because DFA has only one bit memory?
143 views

510 views

### If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

I've seen in previous exams that professors marked the theory as correct: If $L$ is CFL and $\overline{L}$ is CFL, then L is regular. I just don't see how this would work. How would we prove such ...
72 views

### Is the following language context-free? $L= \{a^nb^m| m\geq2^n\}$

Is $L=\{a^nb^m|m\geq2^n\}$ a context-free language?
229 views

### Is this language context free?

In a recent test, I was asked to recognize if the below language is context free: $\qquad\displaystyle L = \{0^{n+m}1^{n+m}0^m \mid n,m \geq 0\}$ I think it is context free, and can be accepted by ...
559 views

### Is $a^n b^n$ an artificial language or does it occur in the real world?

The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$. Do such forms occur in the real world? Can you provide an ...
51 views

### Is this theorem about left-factored grammars correct?

I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor: A CFG grammar cannot be left-factored if all ...
603 views

### Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
217 views

### Pumping lemma for {w | w = ddd}

I want to use the pumping lemma to show that the following language is not context free: $$L = \{w \in \{a,b\}^* \mid \exists d \in \{a,b\}^*, w=ddd \}$$ We suppose that $L$ is context-free. Then ...
14k views

### Is the complement of { ww | … } context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? I'...
114 views

### Looking for a contex-free grammar for the following language

I want to derive a context free grammar for the following language on alphabet $\Sigma=\{a,b\}$: $\qquad\displaystyle \{ xax'yby'z \mid x,y,z\in\Sigma ^*, |x|=|x'|, |y|=|y'|, |z|=|x|+|y|\}$ I am ...
199 views

### Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not

I'm having trouble with this particular language: $$\{a^i b^j c^k \mid i+j \le k\}$$ If it's not context-free, I don't know how to correctly apply the Pumping Lemma for CFLs; if it is context-free, I ...
385 views

### Binary operators with higher precedence than unary operators

Generally (perhaps always) in programming languages, unary operators have the highest precedence. In some langauges, such as Standard ML, one can dynamically change the precedence of binary operators ...
247 views

### Relative complement of a Non CFL to CFL

Let $L$ be a given Context Free Language over the alphabet $\{a,b\}$. Now consider $$L_1=L-\{xyx\ |\ x,y\in\{a,b\}^*\}$$ I know that $\{xyx\ |\ x,y\in\{a,b\}^*\}$ is not Context Free (by using pumping ...
285 views

### Is the language of all ucv with u ≠ v context-free?

Is $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^* , w_1 \neq w_2 \}$ a CFL? In my opinion it is not since if we want to know the inequality of $w_1$ and $w_2$ we must be aware of their equality and that is ...
21k views

### Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
142 views

### What does the symbol # mean when it comes to languages

Given the following: $$\{ w\#x \mid w^R \text{ is a substring of x, with x and w \in \Sigma^*} \}$$ What does $w\#x$ denote?
210 views

### Why is this not a regular language

So I recently had a problem where I had to create a regular language. After consulting my professor on my solution he told me it was close to correct but to check my definition of a regular language. ...
13k views

125 views

### help with the probability of acceptance of a Nondeterministic Pushdown automata

I have this nondeterministic pda: $$\Sigma= \{a,b,c\}$$ and  L=\{\omega\ \epsilon\ \Sigma^*\ |\ \omega\ = \alpha\beta\beta^R\gamma\ and\ \alpha,\beta,\gamma\ \epsilon\ \Sigma^*\ and\ |\beta|\ &...
804 views

### Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.

Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗. This is what I ...
275 views

### Context free language and the complement of it

Given the language $L_1 = \{a^i b^j c^k \mid i \neq j \vee i \neq k\}$, I need to determine whether it is context-free by using the pumping lemma. I must do the same for the complement of this ...
628 views

### Converting to Chomsky normal form

Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form. I have S -> abC | babS | de C -> aCa |b I know what to do with the case ...
135 views

1k views

### Rules regarding Chomsky Normal Form (CNF) grammars

I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions: Can I use a single variable (a non-terminal) on the left-hand side of multiple rules? Can I ...
### Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?
I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(aa)?(aa) and I convert it to a grammar: G ::= A B A ::= C | (...