All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
98 views

How can I quickly guess if L is context-free or det. context-free?

I have a language, for example $\{a^m b^n c^n \mid m, n \in \mathbb{N}, m = 2n\}$ $\{a^l b^m \mid l, m \in \mathbb{N}, l=4^m\}$ How can I see at a glance whether the language is deterministic ...
0
votes
0answers
19 views

Pumping Lemma for CFG - How to do it? [duplicate]

I'm literally so confused on how to even start this problem of proving that the given language is not Context Free. L = {a^i b^j c^k d^l | i = k and j = l} I ...
0
votes
0answers
51 views

Why is this language is not context-free? [duplicate]

Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this ...
0
votes
2answers
657 views

Intersection of a language with a regular language imply context free

Lets say you have a language $L$ and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is ...
0
votes
2answers
306 views

Complement and Context Free Surprising

Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free? $$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$ $$L_{2}= \{w_{1}...
0
votes
1answer
216 views

NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$

I believe that the following NPDA accepts the language $$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$ where $n_a(w)$ represents number of symbol $a$'s in string $w$. Is there a two-state NPDA that ...
8
votes
1answer
1k views

Techniques to prove a language is not DCFL

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL. Are there any other techniques that will help me to ...
1
vote
1answer
264 views

Closure properties between 2 languages of different types [duplicate]

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
1
vote
1answer
343 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
6
votes
1answer
206 views

Is there $L$ such that $L$ and $\bar L$ are context free, but $L$ is not deterministic context free?

The usual candidates for context free languages whose complement is also context free, but they are not regular are the Deterministic Context Free Languages ($DCFL$). For example, $L=\{a^nb^n\mid n\...
-1
votes
1answer
2k views

Create CFG and pushdown automaton for {ww} [duplicate]

I've been trying to make a CFG, a pushdown automaton and a regular expression for the language $\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$. I understand how the reverse of the ...
0
votes
1answer
170 views

What context free grammar generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$ [duplicate]

I am struggling to think of the context-free grammar that generates the language $L(G) = \{a^ib^jc^{2i}d^m\}$, where $i$, $j$ and $m$ are natural numbers. Also, in general, are there any good methods ...
-1
votes
2answers
924 views

Pushdown Automata: CFG to PDA

I have the following grammar for a context-free language: $G = (\{S,A,B\}, \{x,y,z\}, P, S)$ with $P = \{S \rightarrow A, A \rightarrow xAz, A \rightarrow xBz, B \rightarrow y\}$ My question is: How ...
0
votes
2answers
98 views

what is the best way to approach the construction of nondeterministic PDA's?

I'm trying to construct a PDA for $L = \{w0^i1^j \mid w\text{ ends in } 01 \wedge 2i=3j\}$. My understanding is that I have to first accept an arbitrary number of zeros and ones and then ...
0
votes
1answer
84 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?
2
votes
1answer
2k 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) ...
1
vote
2answers
4k 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\}$ and ...
3
votes
3answers
154 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 context-free ...
5
votes
1answer
368 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 ...
7
votes
2answers
789 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 ...
3
votes
1answer
963 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
238 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
340 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 ...
5
votes
3answers
2k 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 really ...
4
votes
2answers
749 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
2k 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
70 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 $...
3
votes
1answer
275 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 ...
1
vote
1answer
103 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 ...
6
votes
2answers
7k 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 ...
3
votes
2answers
27k 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\}\,.$$ ...
6
votes
3answers
262 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
510 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
2answers
4k 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 (...
1
vote
1answer
3k 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
102 views

Creating a CFG that connects lengths of three blocks [duplicate]

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 ...
8
votes
1answer
426 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$. ...
1
vote
1answer
3k 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 ...
0
votes
1answer
323 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
2k views

Show that $0^i$ where $i$ is a power of 2 is not context free [duplicate]

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 = ...
3
votes
1answer
495 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 ...
5
votes
3answers
5k 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 ...
0
votes
1answer
117 views

Intersections of some context-free languages

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
3
votes
2answers
2k views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...
8
votes
1answer
4k views

Are DCFLs closed under reversal?

According to this chart, DCFLs are closed under reversal. However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and ...
0
votes
2answers
5k views

Finding context free grammar for this language?

I needed help finding the context free grammar of this string $$ 10^{n}10^{n}1 $$ So far an idea I have is $$ S\rightarrow 1S1S1\mid 0S \mid \varepsilon $$ Any assistance you can provide would be ...
6
votes
1answer
536 views

Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?

The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}...
10
votes
1answer
461 views

Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
1
vote
1answer
859 views

Unambiguous CFG for $a^ib^j$ where $i \le j \le 2i$

could you please help me for finding an unambiguous CFG for the following expression: $a^ib^j$ where $i \le j \le 2i$
1
vote
1answer
118 views

Context Free or Context Sensitive and why

I was given two languages $$L_1=\{0^k1^k0^m\mid k,m \in \mathbb{N}\text{ and }k < m\}$$ and $$L_2=\{a^mb^{m+1}\}$$ and I was asked to prove whether they are context free or sensitive. For $...

1
8 9
10
11 12
14