A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# 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
280 views

### Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar

How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar Like for grammar $G$ with the following rules $S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$
120 views

### Does the following transformation preserve context-freeness?

I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always context-...
253 views

### Is The Following Language Regular? [duplicate]

Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$. $$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$ Assume that $L_{1}$ is regular and $L_{2}$ ...
320 views

### Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
603 views

### Are there languages generated by linear grammar which aren't regular?

Are there languages generated by linear grammer which aren't regular?
133 views

149 views

### Show how a sentence can be produced from a grammar (Dragon book 2.1)

In the Dragon book (Aho, Sethi, Ullmann) there is one exercise I don't get. Chapter 2, Exercies: 2.1 Given the context-free grammar $$S \to S S + \mid S S * \mid a$$ Task: Show how the signs ...
16k views

### Regular Expression to Context-Free Grammar

Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
11k views

### Push down automata for $\{a^n b^n c^n | n \ge 0\}$

I am learning about context free languages. I understand how $\{a^n b^n c^n | n \ge 0\}$ can be shown to be not context free using the pumping lemma for CFL's. Intuitively however it seems that a ...
4k views

### Easy proof for context-free languages being closed under cyclic shift

The cyclic shift (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this ...
252 views

### Type inference in compiler is context sensitive?

Have read in Compiler textbook that type inference is context sensitive. Can anyone explain why is it so? This means that we need context sensitive grammar in semantic analysis phase of a compiler ...
122 views

764 views

### Pumping lemma problem - Choosing the right string to pump

I have a problem finding the right string to pump for the following language: $$L_1 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\}$$ Which string should I choose to pump? The problem is that I ...
518 views

330 views

### Is $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?

Is the language $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free? Note: $x^R$ is the reverse of $x$. My Work: I think this is a context free language. Since a pushdown ...
14k views

### What is complement of Context-free languages?

I need to know what class of CFL is closed under i.e. what set is complement of CFL. I know CFL is not closed under complement, and I know that P is closed under complement. Since CFL $\subsetneq$ P I ...
150 views

### Generate the word using this grammar

Using this grammar, over the alphabet $\Sigma=\{a\}$  S \rightarrow a \\ S\rightarrow CD \\ C\rightarrow ACB \\ C\rightarrow AB \\ AB\rightarrow aBA \\ Aa\rightarrow aA \\ Ba\rightarrow aB \\ AD\...
215 views

### Closure properties of languages

Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$(For example, let $P = a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always ...
697 views

### Deterministic context-free languages are closed under regular right-product

I am looking for a proof for the following problem: For languages $L$ and $R$, if $L$ is deterministic context-free and $R$ is regular, then $LR$ is a deterministic context-free language. Note:...
314 views

### Grammatical characterization of deterministic context-free languages

Deterministic context-free languages are commonly defined using an automaton concept, the (restricted, deterministic) pushdown automaton. To some that is confusing, as the name context-free refers to ...
13k views

### Context-free Languages closed under Reversal

In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted ...
174 views

### Recursive and regular languages

I'm trying to study for an exam and having difficulty with the following practice questions. Any help would be appreciated. Give a language $L$ such that $L$ is not recursive but $\text{prefix}(L)$ ...
3k views

### Is the complement of $ww^R$ context-free?

Identify the language given by $L = \{ x \in (0,1)^* : x \neq ww^R, w \in (0,1)^*\}$. Note: $w^R$ is the reverse of the string $w$. Closure property can/should be applied only in the cases when the ...