All Questions

Filter by
Sorted by
Tagged with
1
vote
0answers
39 views

Checking correctness of grammar for $L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\} $

I have written a CFG that supposedly generates $L$ below. $$L = \{w \in \{a, b\}^* \text{ }| \text{ } w \text{ has } n_a(w) = 2n_b(w)\}$$ Where $n_a(w)$ is the number of $a$'s in $w$ and similarly for ...
0
votes
2answers
116 views

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?
2
votes
4answers
78 views

Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

I'm trying to prove that the following languague is a regular language: $L=\{ w \mid \lvert w \rvert$ is prime $\}$* What I have thought is to divide each word $w \in L$ into subwords of length 2 if ...
1
vote
1answer
32 views

Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $

I'm trying to find a CFG for the following language: $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ What I thought about unsuccessfully is the following: $S \rightarrow SASBS \mid SBSAS \mid \...
1
vote
1answer
20 views

Closure of context-free languages under left-half [duplicate]

The regular languages are known to be closed under the operation "left half": $$ \operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \...
2
votes
2answers
50 views

Infinite prefix-closed context-free languages contain an infinite regular subset

The Problem: Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C ...
3
votes
1answer
54 views

Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL

Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it. I am sorry but I have ...
1
vote
2answers
51 views

Proving that a language is a CFL

Assume that $L_1 \subseteq \Sigma^*$ is a CFL and that $y \in \Sigma^∗$ is a string. I need to prove that the language $L_2 = \{x \in L_1 \mid x \text{ does not contain $y$ as substring}\}$ is a CFL. ...
0
votes
1answer
33 views

Can PDA accept only by final state without finish reading input?

I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
0
votes
1answer
23 views

Context-free grammar for $ \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$

I know that $L = \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, (l ≥ n) ∨ (l ≥ m)\}$ is a context-free language, because I know the context-free grammar, i.e. $$ S \rightarrow AbZ \mid XBc \\ A \rightarrow ...
21
votes
4answers
2k views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...
22
votes
2answers
468 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
0
votes
1answer
31 views

Grammar for $\{ a^i b^j: j < 2i \text{ and } j \ne i \} $

For the following language, write grammar independent of the text. $$\{a^i b^j: j < 2i \text{ and } j \ne i \} $$ I want a hint to start solving this problem. Where should I start?
-1
votes
0answers
19 views

Is my context free grammar of this language right?

L = { a^m b^n a^o a^p b^q : m >= n, o >= p + q } That's what I tried to do: S -> aSb|bSa|A A -> aA|ε Is my CFG right? I'm missing something? My difficult it's in this part o >= p + q
1
vote
3answers
219 views

Need help understanding what co-recursively enumerable means

Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
-1
votes
1answer
54 views

Is this language a context free language?

Consider the following language, where the alphabet is $\{0, 1, 2\}$: $B = \{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\}$. Is this language a context free language? Prove your answer. I am ...
3
votes
2answers
585 views

Given L is a regular language, prove that Perm(L) is Context-Free

Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the ...
1
vote
1answer
53 views

Exclusion in a context-free language?

I am learning automata theory, and I am confused about this exercise: Give context free grammar to create the following language where the input alphabet is $\{a,b\}$ $L = \{w \text{ where }w\text{ ...
3
votes
2answers
41 views

Language equivalency for modified CFG closed over intersection

Suppose "CFG+" was created, where it is identical to standard context-free grammars in every way, but rather than rules being limited to unions, was also closed over intersections, both ...
14
votes
1answer
513 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 ...
2
votes
6answers
15k 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 \\ ...
2
votes
1answer
142 views

Language of CFG: $S \to aS | aSbS | \varepsilon$

I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I ...
0
votes
1answer
23 views

Words which, cyclically shifted twice, equal their reverse

Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ ...
1
vote
1answer
107 views

Constructing a context-free grammar

I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, ...
1
vote
1answer
193 views

How to prove the language of contractible strings is context-free but not regular?

How to prove this language is context-free but not regular? I can't figure out it. A string is contractible if there is a sequence of contractions which result in the empty string, where a ...
0
votes
0answers
16 views

L= ${ a^mb^nc^pd^q: m+n<>p+q }$ context free? [duplicate]

I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it. Can someone suggest a grammar for this?
0
votes
1answer
56 views

Which of the following words is in the language of the grammar G?

This is taken from a practice quiz by my university. I ruled out that aabbbaab is not part of the grammar: S → aSb → aaSbb... This shows that I can't make this word because it would have to have ...
9
votes
2answers
11k views

Why are CFLs not closed under intersection?

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that ...
0
votes
1answer
48 views

How can I make the following grammar unambiguous

Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y My attempt: ...
1
vote
1answer
61 views

Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free

I have a question about the pumping lemma for context-free languages. I understand the conditions of the pumping lemma. Assume $L$ is context-free. Let $n>0$ be the pumping length given by the ...
5
votes
1answer
3k views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
0
votes
0answers
18 views

generating strings from this formal grammar [duplicate]

Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
2
votes
1answer
44 views

Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL

I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language. so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free ...
1
vote
1answer
32 views

Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $

Is there any difference between saying $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ with $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $? I know that for $v = abab$ we have $v \in L_1$ and $v \in L_2$ my ...
0
votes
1answer
77 views

Using the pumping theorem to show that this language is not context-free

Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free. I really don't know where to start, ...
2
votes
4answers
84 views

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular So far I know that: There are examples where $L$ ...
1
vote
2answers
63 views

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

I have found an exercise where it tasks to provide a grammar and a pushdown automata for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$ While finding a pushdown automata for it is quite easy (four states and two ...
4
votes
6answers
20k views

Context-free grammar for language with unequal numbers of a and b

I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e. $$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$ but ...
1
vote
1answer
56 views

Number of sentences and sentential forms generated by a grammar

In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition: ...
5
votes
1answer
705 views

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
0
votes
1answer
25 views

Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?

How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?
2
votes
2answers
615 views

What are the modern alternatives to Backus–Naur form and what are their advantages?

I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of ...
1
vote
1answer
45 views

Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$

I would like some help for the computation theory. There is a PDA that accepts the language $\{0^n 1^a 2^b \mid n = a+b\}$, so how can I express it into context free grammar? Any help would be ...
2
votes
2answers
3k views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
0
votes
1answer
35 views

Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$

Given the following language, I am tasked with giving a context-free grammar that generates it. $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$ Would this be correct? $A \rightarrow aaaA$ $B\...
0
votes
1answer
39 views

Formal proof of language accepted by a specific CFG

Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align} Please provide a formal proof for the following ...
0
votes
1answer
38 views

Is this an unambiguous CFG that is not LR(k) for any k?

The grammar is this: $$S \rightarrow a B c $$ $$B \rightarrow b B b $$ $$B \rightarrow \epsilon $$ The LR(1) states that I worked out were these $$(1)$$ $$S \rightarrow .aBc$$ $\\\\$ $$(2)$$ $$S \...
0
votes
0answers
14 views

Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
3
votes
0answers
128 views

is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
4
votes
1answer
326 views

Undecidability of “is this CFG prefix-free?”

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition). Another thread has the very different question "...

1
2 3 4 5
14