# Questions tagged [context-free]

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

1,684 questions
Filter by
Sorted by
Tagged with
14 views

### What is the name of the diagram used in JSON spec for representing a context-free language?

If you go to the JSON spec page : https://www.json.org/json-en.html, then you'll see the language represented by some diagrams showing graphically what the language looks like. I wondered, does this ...
26 views

### Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
3 views

### Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
4 views

### Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]

Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
37 views

### L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of y

How can I convert this context free langauge to conext free grammar? Please help I can not solve this problem for days. L = {xy : x, y ∈ {a, b} ∗ , |x| = |y| and x ̸= y^R} where y^R is the reverse of ...
39 views

### How do I convert this context free language to context free grammar L1 = {0^i 1^j : i ̸= j, j ̸= 2i} [duplicate]

How do I convert this cfl to cfg L1 = {0^i 1^j : i ̸= j, j ̸= 2i}
1 vote
366 views

### Does there exist an context free language L such that L∩L^R is not context free?

By the closure property of context-free languages, if $L$ is context-free, then $L^R$ (the reverse of $L$) is also context-free, but $L\cap L^R$ might be non-context-free. I tried to come up with an ...
58 views

### Can we give an example Context-Free Language that a DPDA can not recognize [duplicate]

Can we give an example Context-Free Language that a DPDA can not recognize. If we DPDA can not recognize can you explain why?
51 views

### Derivation trees to show a given grammar is ambiguous

Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string ...
29 views

### Proof that $\{0^m 1^n : 0\le m\le n^2\}$ is not a CFL

I am trying to prove by the pumping lemma that $L=\{0^m1^n:0\le m\le n^2\}$ is not a CFL. Here is what I have so far. Suppose for contradiction that it is a CFL and let $N$ be the pumping length. ...
57 views

### Is L={0^n 1^n ∣n≥0} context free language?

I looked through many sources which give this as an example for cfl. It also makes sense according to this: But it fails the pumping lemma test. Let's take n=5. According to the Pumping Lemma, we can ...
26 views

### Which one is an LL(2) but not an LL(1)

I'm pretty sure b and d are ll2 and not one but not 100% sure. (a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ B → aBb | Ʌ (b) S → aaScc | aaBbc | aBb | ac | Ʌ B → aBb | Ʌ (c) S → aaScc | aaBbc | B | ac |...
52 views

### Turing machine for a^n b^m c^n d^m

The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
31 views

### Language of words concatenated with themselves

Let $L$ be a regular language. Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?
33 views

### An elementary question about grammar

Recently, I am studying grammar in automata. And, I have few information about this subject. I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$. Is it true if I say that $S\to aASA$ ...
36 views

### Write a CFG for a language of the form L_1 ={a^ib^jc^kd^m|i,j,k>=0, i +j +k> m}

I'm currently having trouble coming with context free grammar to describe this language. My current intuition is to generate an arbitrary amount of a,b,c's on my string and then whenever the character ...
59 views

### Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s

Let P be the language of palindromes over the alphabet Σ = {0, 1}. and let P‘ be the subset of the palindromes with different numbers of 0s and 1s. Is P' context-free? I know that for the language of ...
1 vote
30 views

### How need help to specify a grammar for arithmetic expressions

I am trying to come up with a grammar for arithmetic expressions with the following order of operations: Parentheses Factorials Exponents Functions / unary plus and minus Juxtaposition (implied ...