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

learn more… | top users | synonyms

3
votes
0answers
32 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
0
votes
1answer
22 views

If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$

I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?
-1
votes
1answer
32 views

Proving that the set of non-universal CFGs is not in NP

How do I prove that $\overline{\mathrm{ALL_{CFG}}}$ does not fall in NP, where $\qquad\mathrm{ALL_{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG}, L(G) = \Sigma^* \}$
1
vote
2answers
37 views

How can this grammar parse such an input?

I've an example which I simply don't get at all. Implement an attributed grammar that checks that either the word ends in $b$ or each prefix of the word contains at least as many $b$s ...
1
vote
1answer
40 views

Language of binary strings divisible by 7

There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is : 1) Recognizable by a finite-automaton. 2) ...
0
votes
1answer
25 views

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$ [on hold]

Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$. I just wanted to check if my grammar is correct or not. $$A ...
1
vote
2answers
57 views

PDA recognising all strings with a $1$ in the second half

My professor gave us an old exam to look over for our final exam and I am having a hard time understanding the push down automata problem he gave. In the problem it says: Let $\Sigma = \{0,1\}$ ...
3
votes
2answers
68 views

Decide if this language is context free

I got this question for homework: Decide if this language is context free or not: $\qquad \{x@1^m: x \in \left\{0,1\right\}^*, m \in \mathbb{N}, x_m = 1\}$. Intuitively I think it's not ...
4
votes
1answer
42 views

Do an ambiguous grammar and its corresponding unambiguous version generate the same language?

If I have an ambiguous grammar G and its disambiguated version D. Then which one is true L(D) ⊂ L(G) , L(G) ⊂ L(D) or L(G)=L(D)? As I tried with some examples to transform a grammar to it ...
6
votes
1answer
249 views

Parikh's Theorem: CFL's “contain” regular languages?

The first sentence of the Wikipedia article for Parikh's Theorem states: "Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of ...
-2
votes
0answers
36 views

A quick question about context free languages and polynomial reduction [duplicate]

If we let L1 be a context-free language and L2 = {0^n1^n : n ∈ N}, then would L1 ≤P L2? since L2 is also a context free language, and that would mean they are both decidable, aren't all decidable ...
0
votes
1answer
27 views

Help me find the ambiguity in this grammar

I've been sitting on this for 20+ minutes and can't seem to generate a string that is ambiguous. Can anyone help me? The grammar is: $$S \xrightarrow{} SS \mid T$$ $$T \xrightarrow{} aTb \mid ab $$ ...
2
votes
2answers
44 views

Context-free grammars and priority

This grammar is supposed to give priority to multiplication: E -> E + T | T. T -> T * F | F. F -> x. A derivation for "x + x * x" would be (unless I'm wrong): E => E + T => T + T => F + T => x + ...
0
votes
1answer
61 views

Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?

In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \{0,1\}$. $PAL = \{w \in \{0,1\}^* : w = w^R\}$. We have proved that every string in this language ...
3
votes
2answers
84 views

Can every context free language written as a intersection of another context free language and a regular language?

I'm preparing an Formal language exam, One question from previous year's final is: Prove or disprove:If L is a context free language, then there exists a language P that is generated by a pure ...
1
vote
1answer
135 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
-2
votes
0answers
25 views

Context Free Grammer (CFG) for Language [duplicate]

This is the language I have: $\{t^{4n} s^m t q^{m+n} s^4 \mid m,n \geq 0\}$ and I am absolutely confused as to how to turn it into CFG. Any help? Thanks! So $\{a^{n} b^n\}$ can be written as S = ...
0
votes
1answer
25 views

Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?

As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at any order. Does that mean it has to be cyclic, and therefore ambiguous? I ...
-1
votes
0answers
28 views

Inclusion of Context-Free languages is undecidable

So, I'm having a hard time with this one. Consider the language: $$\text{INLC}_\text{CFG} = \{\langle G_1, G_2 \rangle \mid \text{$G_1$ and $G_2$ are CFGs with $L(G_1) \subset L(G_2)$}\}$$ I need ...
3
votes
3answers
227 views

How to represent whitespace in a context-free grammar?

Say we want to support: xx The following grammar does accept it: S -> xAx A -> ε. because S => xAx => xx. But what about supporting: x x I realize this might be a stupid question but I'm ...
0
votes
0answers
45 views

Can we say we reduced a rule if we reduced an equivalent set of smaller rules?

I have constructed an SLR(1) parsing table with the following rules. S -> S + S + S (rule 1) S -> S + S (rule 2) S -> y Is reducing rule 2, then shifting + and y, then again rule 2, equivalent ...
-1
votes
0answers
14 views

Transform a Grammar G into LL(1)

I have the following grammar and I need to convert it to LL(1) grammar G = (N; T; P; S) N = {S,A,B,C} T = {a, b, c, d} P = { S -> CbSb | adB | bc A -> BdA | b B -> aCd | ë C -> Cca | bA | a } The ...
-3
votes
1answer
18 views

Eliminating Null Productions from Context Free Grammar

Here is a problem I am trying to solve: S -> 0A0 | 1B1 | BB A -> C B -> S | A C -> S | e I know that C is nullable (since it produces an epsilon) and ...
4
votes
2answers
70 views

Prove or disprove: L^2 context free implies L is context free

Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language L. I was trying to prove that L^2 is context free which ...
-1
votes
1answer
34 views

Proving correctness of a CFG by induction on length of strings generated [duplicate]

Consider the following grammar with starting symbol of $S$. $$S \rightarrow 0S11\;|\;S1\;|\;0$$ Let $L = \{0^i1^j:\; \ge 1\; and\; j \ge2i-2\}$ . Give a formal proof of the following claim : For all ...
0
votes
0answers
46 views

Designing CFG for sequences of words of which two arbitrary ones are reversals

Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because ...
-2
votes
1answer
41 views

How to write CFG for languages [duplicate]

How do you write the CFG for the following language: {ax by c ax+y} Is there some formula or rules I need to follow? An explanation will be so appreciated. What I tried is: First I broke ax+y into ...
3
votes
1answer
75 views

How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If ...
2
votes
0answers
29 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third [duplicate]

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ ...
0
votes
1answer
21 views

Reversing a List from a Context-Free Grammar

Let's say I have a struct_declaration_list of the following type. How do I reverse it? ...
1
vote
1answer
43 views

Applying the context-free pumping lemma to a language with crossed nestings

For proving language $\{a^nb^mc^nd^m \mid n,m > 0\}$ is not context free. Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length? Or do I have to use a string that ...
0
votes
0answers
15 views

How to create a context-free grammar? [duplicate]

I am learning compilers and I am troubled by how to create the context-free grammar of a language. Is there a method I can follow to create the context-free grammar for most language ? I'm new to this ...
1
vote
2answers
65 views

Converting to CFG from a CFL? [duplicate]

I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me. Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
1
vote
2answers
55 views

Is $a^n b^n c^n$ context-free? [duplicate]

I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language $$\{a^nb^nc^n\mid n\geq 1\}\,.$$ ...
5
votes
3answers
94 views

Prove that the complements of pumping-style languages are context-free

Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$. Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$ Clearly, $L$ is a CFL, as it is generated by the ...
4
votes
1answer
111 views

Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities

Prove that if a CFL $L$ is inherently ambiguous, then for any grammar $G$ with $L(G) = L$, there are infinitely many strings in $L$ that have (at least) 2 different derivations in $G$. Here's a ...
0
votes
1answer
51 views

PDA - Sum of Two Characters = Sum of Two Other Characters

For one problem I have to solve, I'm given a Language: L = {a^r b^s c^t d^u | r+s = t+u} And from it told to construct a PDA that accepts it. I can construct a ...
0
votes
2answers
93 views

Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

This question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was, Consider the following six classes of languages: Context free ...
-3
votes
2answers
44 views

Pumping Lemma for Context-Free Languages for reversal language [duplicate]

Show that the language L = {ww^Rw: w in {a,b}*} is not a context-free language.
2
votes
2answers
127 views

Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
1
vote
1answer
85 views

Find a CFG for the set of prefixes of a CFL [duplicate]

How do i generate grammar for Prefix of Langauge L, SupposeG=(V,􏰀,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈􏰀∗ : ∃ y such that xy∈L}. I understand for ...
3
votes
1answer
51 views

Creating a CFG that connects lengths of three blocks

I have to create a CFG which generates $$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$ The first part is easy enough, I came up with $$\begin{align*} S &\to ...
6
votes
1answer
125 views

If L is context-free, must FH(L) be context-free?

Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that } xy \in L\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. ...
0
votes
1answer
132 views

Is Context Free Language closed under perfect shuffle?

Note that this is not shuffle but perfect shuffle, defined as follows: Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle ...
1
vote
1answer
62 views

Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
0
votes
1answer
43 views

Help understanding formal language notation

I am reading this text and it is making absolutely no sense to me. It as if it assumed I will understand. Not to mention the writer apparently had a book made and his grammar is poor. Some of the ...
2
votes
2answers
94 views

Show that 0^i where i is a power of 2 is not context free

I'm having difficulty trying to use the pumping lemma in order to show that $L= \{0^i \mid \ i \text{ is a power of 2 }\} $ is not context free. I"m starting by stating that $ s = 0^p$ and then $ s = ...
2
votes
1answer
40 views

Show that the string $( [ ) ]$ is not in a Dyck language

I think I understand why the string $( [ ) ]$ is not in a Dyck language. In my words, D2* is all the dyck words of 2 parentheses. From the definiton of $D2*$, every words must have exactly 2 ...
4
votes
1answer
459 views

Is CYK still relevant today?

I've come across the CYK algorithm and was wondering, as it's quite old, if it is still relevant today. Is it or an extension of it still being used in compilers (for example), or have other ...
3
votes
2answers
292 views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...