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.

Filter by
Sorted by
Tagged with
3
votes
1answer
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$
9
votes
1answer
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-...
2
votes
1answer
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}$ ...
10
votes
1answer
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 ...
1
vote
1answer
603 views

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

Are there languages generated by linear grammer which aren't regular?
-3
votes
1answer
133 views

Regular and context free languages

I need to determine if the following languages are regular / context free and to explain. Please help me with that. $$L_1 = \{ a^{i_{1}}b a^{i_{2}}b a^{i_{3}}b a^{i_{4}}b a^{i_{5}}b a^{i_{6}}b a^{i_{...
2
votes
1answer
1k views

Context Free Grammar for language L

Can someone help with this: $L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$ I'm trying to write a grammar for this language? I tried this: $S \to S_1 \mid S_2 \\ S_1 \to aXb ...
3
votes
1answer
137 views

Prove that $\{0^n 1^{n\cdot m} : n,m \in \mathbb{N}\}$ is not context-free

This is a homework problem I have spent several hours on. A "hint" is given that we may use this fact: If $n,j,k \in \mathbb{N}$ satisfy $ n \geq 2$ and $1 \leq j+k \leq n$, then $n^2+j$ does not ...
7
votes
2answers
12k views

Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}

Can someone help with this: $L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$ I'm trying to write a grammar for this language? I don't know how to do this. I tried this: $S \rightarrow aaAb \...
3
votes
3answers
4k views

How to convert a context free grammar (could generate regular language) to a right-linear grammar

Consider the context free grammar: $$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$ It could generate regular language, which means it can be converted to a right linear grammar. Is ...
2
votes
2answers
1k views

Can a CFG end have a non-terminal symbol in the middle of it?

What is the correct way to write a CFG? A -> B C' E C' -> C C' -> null or A -> B C' C' -> C E C' -> E
1
vote
1answer
64 views

General start rule question for a context free grammar

Suppose I have a context free grammar described: $S \rightarrow 0SS1$ $S \rightarrow 1$ $S \rightarrow \epsilon$ Because the first rule is considered the start rule does that mean ...
5
votes
3answers
824 views

Give a grammar to show whether a language is regular or context-free

I have to generate a grammar for the language $L = \{ w \in \{ a, b\}^* \mid |w| \in 2\mathbb{N}, w \neq w^R\}$ and give the type of the language. I've generated the grammar $\qquad \begin{align} ...
1
vote
0answers
78 views

Are these two languages context free? [duplicate]

Possible Duplicate: Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free Do there exist context-free grammars for the following two languages: The set of all strings of the form $xx$ where ...
7
votes
4answers
1k views

Where do the length restrictions of the pumping lemma come from?

For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows: Regular version: If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following ...
1
vote
1answer
988 views

Facebook Hackercup 2013: Balanced Smileys

On Facebook HackerCup 2013, they asked the following question: Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express ...
5
votes
2answers
353 views

What's the reason for the second condition of the pumping lemma(s)?

For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows: Regular version: If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following ...
2
votes
1answer
44 views

Is there a name for this relation on CFGs?

I'm looking for the name (or a name if there isn't one already) of this relation between $G_1=\left<\Sigma_1,\mathcal{N}_1,\mathcal{R}_1,S_1\right>$ and $G_2=\left<\Sigma_2,\mathcal{N}_2,\...
0
votes
0answers
55 views

How i can use Mathematical induction to prove CFG production? [duplicate]

If I have production $G_n$ $S \rightarrow A_i b_i \quad$ for $1 \le i \le n$ $A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$ Prove $G_n$ is sub-productions from $2n^2 - ...
0
votes
1answer
178 views

Could anyone prove that this is a context free language or not? [duplicate]

Possible Duplicate: Show that $\{xy \mid |x| = |y|, x\neq y\}$ is context-free Can anyone prove that the following is a CFL? or not? why? $$L=\{w=w_1w_2 \mid len(w_1)=len(w_2) \mbox{ and $w_1$ ...
0
votes
1answer
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 ...
7
votes
3answers
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?
3
votes
3answers
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 ...
11
votes
3answers
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 ...
4
votes
1answer
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 ...
2
votes
1answer
122 views

Pumping lemma problem

I need some help with the following question: One of the languages $$L_1 = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$ $$L_2 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\...
1
vote
5answers
10k views

Explaining why a grammar is not LL(1)

I need some help with explaining why a grammar is not LL(1). Let us take the following grammar: $$ \begin{align} S \rightarrow & aB \mid bA \mid \varepsilon \\ A \rightarrow & aS \mid bAA \\ ...
1
vote
1answer
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 ...
1
vote
1answer
518 views

Pumping lemma for Context-Free Languages

I have a question about a specific pumping lemma problem for Context-Free Languages. Suppose we have the following Language: $L = \{a^{i}b^{j}c^{k}d^{l} \mid 0 < i < k \wedge j > l > 0 ...
1
vote
1answer
485 views

Deciding whether a Language is Context-free/Regular/Non Context-Free

I need some help with deciding if a given language is regular, context-free or not context-free. Lets' say I have the following languages over the alphabet $\mathcal{A} = \{a,b,c,d\}$: $$ \begin{...
-1
votes
1answer
1k views

Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
0
votes
1answer
109 views

Derive some strings

G=({S,A,B},{0,1},P,S) Where P: S→A1B A→0A|ε B→0B|1B|ε I have to list the first 25 strings from L(G). So far I've made the tree, but I'm not sure that it's correct.
4
votes
3answers
582 views

Is this grammar really LL(1) while not being LR(1)?

$S \rightarrow S$, $L(G) = \{\}$ LL(1) analysis: We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$. $FIRST(S)$ doesn't contain ε, so the parse table looks like this: ...
2
votes
2answers
5k views

How to show that given language is unambiguous

Given following grammar: $$ \begin{align} S \rightarrow &A1B \\ A \rightarrow & 0A \mid \varepsilon \\ B \rightarrow & 0B \mid 1B \mid \varepsilon \\ \end{align} $$ How can I show that ...
2
votes
2answers
544 views

Is this a regular grammar?

I went through a question asking me to categorize the following grammar. $$S → AA, S → AB, A → a, A→BB, B → b, B → e$$ From the production rules, clearly it is Context-Free. But it accepts a finite ...
2
votes
3answers
6k views

How does one make an unambiguous context-free grammar for arithmetic expressions?

Say I have a context-free grammar defined by the following rule. $$ \langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\...
2
votes
2answers
119 views

How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free?

Let $A$ and $B$ be two deterministic finite automata. How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free? Intuitively, I feel that $L_E$ should ...
3
votes
1answer
301 views

Is this a Context Free Language?

I got this question on my final exam: Is the following language context-free? $$ L = \{w\bar w^R \mid w\in \{0,1\}^* \}$$ Notation: The string $\bar w$ is obtained from $w$ by replacing all 0s ...
16
votes
1answer
8k views

Construct a PDA for the complement of $a^nb^nc^n$

I am wondering if this is even possible, since $\{a^n b^n c^n \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n \mid n \geq 0\}$ from the rest of $...
3
votes
2answers
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 ...
11
votes
3answers
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 ...
1
vote
2answers
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\...
1
vote
1answer
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 ...
5
votes
1answer
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:...
6
votes
2answers
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 ...
8
votes
3answers
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 ...
2
votes
1answer
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)$ ...
0
votes
1answer
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 ...
3
votes
1answer
2k views

LR(1) - Items, Look Ahead

I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ? Say for an example that I have the following grammar: S -> AB A -> aAb | b ...
3
votes
2answers
3k views

CFG and PDA for the grammar that has perfectly nested parentheses and brackets

I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets. $\qquad\begin{align} S &\to [S] \\ S &\to (S) \\ S &\to SS \\ S &\to \varepsilon \...