# Questions tagged [context-free]

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

1,687 questions
Filter by
Sorted by
Tagged with
13 views

### When finding the CNF of a CFG, in the step where you eliminate unit productions, does order matter?

Suppose a CFG has unit productions A -> B and C -> D among other productions, possibly involving ...
• 315
1 vote
80 views

### Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $G$ for $$L = \{a^i b^{i+j+k} c^j d^k\}$$ so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
101 views

### How to write a grammar with a low-precedence unary postfix operator?

Like this person on Google Groups, I'm trying to understand how to write a grammar involving Wolfram Language's low-precedence unary & operator. The operator ...
• 121
1 vote
616 views

### CFG for the language {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}

The question is the following: Construct CFG for the L = {w ∈ {0, 1}∗ : w is a palindrome and |w| is divisible by 3}. I am able to construct CFG for the set of all palindromes as below: S --> aSa | ...
82 views

### Example 7.1 correctness in Introduction to Automata Theory, Languages, and Computation

The example says that C is unreachable, but there is the production S-> aBC so C is clearly reachable. This is an error right? or am I missing something.
30 views

### First Set for this grammar? Is it Indirect Left-recursive

Given the grammar (Uppercase alphabet is non-terminal, lower-case alphabet is terminal), how to find FIRST set? A -> mB | CD B -> CBn | epsilon C -> pA | epsilon D -> q This is NOT a ...
• 1
49 views

### Proving that $L = \{a^n b^m |\: m \:\%\: n = 0 \ \}$ is not context-free

For language $L = \{a^n\, b^m\: |\: m \:\%\: n = 0 \}$, that is, 𝑚 is a multiple of 𝑛. I'm trying to find a proof that it isn't a context free. I know it isn't regular, but it also doesn't seem to ...
677 views

### Is the language $L = \{0^i 1^j | i \ne 2j\}$ context free?

I have been trying to find a a CFG for this language generated. I came to the conclusion that I need three parts When $i \le j$ When $j < 2j < i$ When $j < i < 2j$ I was able to come up ...
53 views

47 views

### Generating parse trees when only a recognizer is given

I am trying to understand "On the complexity of general context-free language parsing and recognition" by Walter L. Ruzzo. One of the results from the paper is about generating a parse tree ...
31 views

### Why $L$ = { $uc^nu$ | $u$ ∈ $P$, $n > 0$ } isn't context-free?

$P$ is the set of all words of even length on {0,1}. Hi, i tried using pumping lemma to see why $L$ isn't a context-free language, but there's a decomposition where none of all three properties is ...
1 vote
26 views

### $|v|$ and $|x|$ factorizations (in Pumping lemma for context-free) have the same length?

When i iterate $v$ and $x$ factorizations to see if a word is still in a language $L$, do i have to assume that $|v| = |x|$ always or could happen theirs lengths are different?. I'm asking because i ...
49 views

### Convert regex for comma separated value to CFG grammar

I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to ...
41 views

### Duplicate rules in CFG

Suppose I have the following CFG that I would like to bring to CNF S -> TA | bA | Ab | b A -> Aa|a T -> Ab Then I have two options to get rid of the ...
• 155
1 vote
37 views

### Which non regular language meets the requirements for pumping lemma for regular languages?

I heard in my lecture that there are non regular languages which meet the requirements for the pumping lemma for regular languages but I never actually saw one. Does anybody have an example?
30 views

### Are $L' = \{uu| u \in P \}$ and $L" = \{uuu| u \in P \}$ context-free languages?

$P$ is the set of all palindrome words. I tried using pumping lemma for context-free languages on $L'$. I've distinguished two possible cases: (Factors = $uvwxyz$) (Iterating factors = $v$ and $x$) ...
52 views

### Are there any updates to CYK parsing that handles epsilon rules in arbitrary nonterminals?

I am a researcher starting to work on the field of parsing and recognition of languages. As part of my background research, I am reading up on CYK. I understand that it requires the grammar to be in ...
96 views

### Is $L = \{w w^r w | w \in a(b+c)^*a \}$ a context-free language?

Can't understand how to apply pumping lemma to see if a language is context-free or not. I tried to verify the context-free's pumping lemma, and the language seems to be not context-free but I can't ...
297 views

### How to use the Pumping Lemma to show that a language is not context free?

I have the following alphabet $\Sigma = \{0,\dots,9\}$ and the following language over $\Sigma \cup \{\#\}$: $$L=\{\#w \ |\ w \in\Sigma^*,\sum_{i\geq1}w_i\ \text{is prime}\}\\\\$$ This language ...
• 105
105 views

### PushDown automata for a^(n) b^(2n) c^(2n) d^(n)

i got this question in a theory of computation quiz "give pda for a^(n) b^(2n) c^(2n) d^(n)" i am arguing that there is no pda for that question but our ta says that we can push 5x to the ...
43 views

### Build a context-free grammar for the language

Build a context-free grammar for the the complementary language of: $L=\{ww^{R}\,\,|\,\,w\in\{0,1\}^{*}\}$ I think $L^C$ is the set of all strings that are not palindromes, but I don't know how to ...
• 99
Build a context-free grammar for the language: $L=\{\#x\#y\#\,\,;\,\,|x|=|y|\,\,\wedge\,\,x,y\in\{0,1\}^{*}\}$ over $\sum=\{0,1,\#\}$ How can I make sure that |x|=|y|?