# Questions tagged [context-free]

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

1,191 questions
Filter by
Sorted by
Tagged with
20 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*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, here. ...
17 views

### Deterministic pushdown automaton for a given language

I am trying to make a deterministic pushdown automaton from this language but without success. Here is the language definition: $\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \}$ ...
33 views

72 views

### Context-free Grammar Exercise

Could someone explain me how to form a context-free grammar with all rules R by this example language, please? \begin{equation} L:=\left\{w c v c \overleftarrow{w} | w, v \in\{a, b\}^{+}\right\} \end{...
3k views

### Is {ww^r ww^r} a context-free language?

Is the language $L = \{w w^r w w^r \mid w \in \Sigma^*\}$ context-free? ($w^r$ is the reversal of $w$.) I heard that by using the pumping lemma, we can only prove that a language is not context-free, ...
25 views

### Creating a parse tree from two productions

How can I create a parse tree from the two productions below \begin{align} S &\rightarrow 0S2\mid 0T\\ T &\rightarrow 1T\mid\epsilon \end{align} ... to show how 0012 has been made?
46 views

### Formal languages: What is $2n_c$?

I have got following question: Determine whether the following language is context free or not: $$L = \{ w \in \{a,b,c\}^*: n_a (w) = n_b (w) = 2n_c (w)\}.$$ What is the meaning of $2n_c$ in the ...
447 views

### Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
37 views

35 views

### Making a CFG for a^i b^j c^k such that i+k < 3j

I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG. I have thought about solving this for a long time but but this still hasn't gotten me ...
154 views

### Example of non-regular context free language L such that prefix(L) is regular

Suppose we have some non-regular context free language L. Suppose we also have language of all prefixes of words in L. What can be an example of non-regular language L such that language of it's ...
71 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 ...
41 views

### Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ...
52 views

### Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$

Prove that grammar $G$ with productions: $S \to aSc|\epsilon | bBc$ $B\to bBc | \epsilon$ Generates language $L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \}$ Step 1. Prove $L(G) \subseteq L$ . ...
19 views

### Variable derives itself

In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim. Consider the grammar:  \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \...
18 views

### Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
18 views

### Finding a Context- free grammar (CFG) for the language [duplicate]

I am trying to find a CFG for the language A below. I have spent hours on this but still could not find the answer. I also came up with the idea that this may not a context- free language but there is ...
254 views

21 views

### Using DPDA instead of LR parsers

If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ...
2k views

### Is Python a context-free language?

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...
39 views

### Does this argument prove CFLs are not closed under union?

Context free languages are not closed under complementation. This follows from their property of non-closure under intersection: If CFLs were closed under complementation, then they must have also ...
71 views

### Context-free grammar for $\{a^x b^y : x \neq y\}$

I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of <...
257 views

### Is {a^n (a+b)^n | n>0} a Deterministic CFL?

$L = \{ a^n (a+b)^n | n>0\}$ A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using ...
11k views