Linked Questions

6
votes
1answer
352 views

Why do we study closure properties of formal languages?

In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is ...
0
votes
2answers
2k views

Existence of non-context free but decidable languages

I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-...
5
votes
2answers
358 views

Why is the following language not context-free?

$L = \{a^n b^m | m \not= n^2 \}$ I guess I need to use Pumping Lemma for CFL in order to prove this. But I'm stuck. Assuming that $ a^n b^m = uvxyz$, we know that $v$ or $y$ can not have both $a$ ...
0
votes
3answers
1k views

Is it possible to prove Language L context-free? [duplicate]

Give a question: Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not. If the answer is yes, can I use the following PDA to prove it? Since {a^n b^(n+m) a^m}={a^n b^n ...
-1
votes
1answer
1k views

Determining whether a context-free language (CFL) described by a given grammar is regular (RL)

In my homework we're given the following problem: Determine whether the context-free language described by the following grammar is regular, showing all the reasoning steps: S -> T T | U T -> 0 T | ...
4
votes
1answer
594 views

A context free grammar proof

There is a problem which I cannot solve. If you give a tip I will be very glad. Prove that following language is not context free: $L= \{ a^nb^m | \gcd(n,m) = 1 \}$. It can be proven using the ...
14
votes
1answer
457 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
3
votes
1answer
566 views

Use the pumping lemma to prove that {www} is not context-free

Use the pumping lemma to prove that the following language is not context-free. $\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$ I am studying for an exam and really trying to understand this question. ...
2
votes
1answer
541 views

How to prove that $L = \{a^n b^m a^n b^m \mid n,m \ge 0\}$ is not a CFL?

I'm stuck with the proof. I've tried Ogden's lemma but it doesn't seem to help. The problem is: Let $N$ be the constant of Ogden, let $z = a^N b^{N+1} a^N b^{N+1}$, and $z = uvwxy$. Now I should ...
0
votes
1answer
534 views

Prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \}$ is not CFG

Can someone help me prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j+3 < k \}$ is not a context free language? I've tried applying the pumping lemma for CFGs and proving case by case (taking ...
2
votes
2answers
313 views

Does this language have a context-free grammar?

Here is a question that I encountered in one of my exams: Find one context-free grammar that recognizes the language: $\qquad L = \{a^n(b^mc^m)^pd^n \mid m, n, p \geq 0\} $ Can you find such a ...
1
vote
3answers
216 views

Deciding if language is Context-Free

I need help with deciding if $L$ is context-free. $$L = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$ Can be rewritten into: $$L = \{a^pb^qb^rc^sd^qd^te^pe^r \mid p, q, r, s \...
1
vote
2answers
152 views

Is a^mb^n where m=n^2 a CFL?

Is $a^mb^n$ where $m=n^2$ a CFL? I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right? On the other hand I ...
0
votes
1answer
500 views

Showing that u#v with u a substring of v is not context-free

I need to find whether this language is context-free or not: {u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#} I suspect that it'...
2
votes
1answer
469 views

Is the language $\{a^n b^n c^i | i \leq n\}$ context free?

I'm trying to apply the CFL pumping lemma. And, I've already tried words $a^pb^p$ and $a^pb^pc^p$. Not sure where to go from here.

15 30 50 per page
1
4
5
6 7 8