# All Questions

670 questions
Filter by
Sorted by
Tagged with
20 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 ...
75 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 ...
32 views

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 ...
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$ ...
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$, ...
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 ...
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?
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 ...
47 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: ...
59 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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
55 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: ...
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?
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 ...
108 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?
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 ...
35 views

49 views

### Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} ) (sorry for the formatting, see screenshot-link for conventional/clear ...
51 views

### The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
32 views

### Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
127 views

### If $A$ is context-free then $A^*$ is regular

I am currently studying for my exam and I am having trouble to solve this question: Right or wrong: If $A$ is context-free then $A^*$ is regular. I think it's wrong because if $A$ is context-free it ...
58 views

### Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...