The 2024 Developer Survey results are live! See the results

# Questions tagged [context-free]

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

1,733 questions
Filter by
Sorted by
Tagged with
164 views

### Understanding a bound for derivation length of any string in Pumping lemma for context-free languages

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz: Let $L$ be an ...
116 views

### Given an CFG determine if $\varepsilon \in L(G)$

Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ? The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (...
1 vote
723 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 ...
109 views

### Intersection of Infinite Regular Language with CFL

Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
1 vote
54 views

### Possible mistake in a book regarding parsing and lexical analysis

I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage : "From a practical point of view, for each grammar G = (Σ,V, S, P) ...
1 vote
51 views

### Rough sketch for an Algorithm to show that a context free grammar G generates only words that are solely made up of b's

The title is a bit long but bare with my english skills. As the title says I have a the task to give a rough sketch for an algorhitm that checks whether a give grammar G, with the alphabet {a,b,c}, ...
100 views

### What could be possible NFA for the RegEx "a?"

I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$ I am wondering if I should deconstruct the RegEx as - Concatenation of $a+$, $(b|c?)$ together with $c$ OR ...
317 views

### What to do following a reduce in LR(1) parsing?

I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what ...
1 vote
49 views

### Alternative solution for the Dangling Else Problem

I understand that one of the ways to solve the Dangling Else Problem is by imposing innermost binding. So, we have to transform the following ambiguous grammar: ...
190 views

1 vote
40 views

### Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$

If a $PDA$ can be constructed to check whether a string is not a computation history for a Turing Machine. Like in the proof of $ALL_{CFG}$ is not decidable. Then we can construct a $PDA$ that accepts ...
323 views

11k views

### Two-State Turing Machine for Parenthesis Matching

In college we have been learning about theory of computation in general and Turing machines more specifically. One of the great theoretical results is that at the cost of a potentially large alphabet (...
218 views

### Variable Repetitions in Pumping Lemma for Context-Free Languages

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in An Introduction to Formal Languages and Automata (5th ed.) by Peter Linz: Let $L$ be an infinite context-...
We are given the grammar rules $A \to F B E$ $B\to A C$ These rules are only some of the rules of a larger grammar $G$, but we are not given the remaining rules of $G$. We are told that $A$ is ...
Consider the language $L$ over the alphabet (,[,),] such that any word $w \in L$ if formed as a shuffle of two (possible empty) well-formed sequence of parenthesis: one over (,) and another over [,]. ...