# Tagged Questions

15 views

### Is the language regular or contextfree?

Could you tell me if the language $$L=\{ w \in \{a,b,c\}^*:$$$$\text{there is at least one time the substring abc and none of the symbols a,b,c is repeated three times} \}$$ is regular or ...
14 views

### Use closure properties for the language $L=\{a^kb^l:|k-l| \leq 100 \}$

Given the language $$L=\{a^kb^l:|k-l| \leq 100 \}$$ I have to show that $L$ is regular or context free using closure properties. I have done the following: The language is regular. Let $k>l$, then ...
21 views

### productions with identical right hand sides for different nonterminals

Can a regular grammar contain two productions with identical right hand sides? I know in context free grammars shift reduce parsers issue reduce reduce conflicts when smth like this happens. What are ...
52 views

### Context Free Language [Prove Or Disprove]

Given the language below: $$L = \left\{w\in (a + b + c)^*: n_a(w) = n_b(w)\text{ or }n_a(w) \ne n_c(w)\right\}$$ How would I prove or disprove that it is either context free. I know that if it was ...
36 views

### Injective map, that maps context-free languages to regular languages

Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular ...
99 views

92 views

### Does the Halting Problem apply when evaluating programs that are regular languages?

Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program ...
115 views

### Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
87 views

### Is $L = \{a^{n+2} b^n | n \ge 0\}$ context free or regular?

Is the language $L = \{ a^{n+2} b^n | n \ge 0 \}$ context free? If so, what is a context free grammar for it? If it is regular, what is a right linear grammar for it?
2k views

### Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
176 views

### Building a regular grammar from NFA

I'm requested to make a regular grammar from a given NFA. In this NFA, there's a "death state", which means, when getting to it, there's no way back to the rest of the states (a self-loop to the same ...
241 views

### Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
198 views

### How to deduce Intersection and Difference of these languages?

$\mathcal{L1}=\{a^nb^n c^m d^m\;|\;m,n>=1\}$ $\mathcal{L2}=\{a^nb^n \;|\;n>=1\}$ $\mathcal{L3}={(a+b)^*}$ How to deduce the Intersection of $\mathcal{L1}$ and $\mathcal{L2}$ is CFG or ...
140 views

### regular expression/languages short questions

I'm stuck on these practice problems. If someone could help me solve them it would be great. What is a contextfree grammar for the langauge $L = \{a^i b^j c^j d^i \mid i,j \ge 0\}$ The following ...
55 views

### Confusion related to context free grammar

If G is a context-free grammar such that it has the productions of the form $$X \rightarrow \alpha Y ,X \rightarrow \alpha$$ How can I show that L(G) is a regular language
84 views

### Pumping lemma - do I have to show every way to split string to have a complete answer?

In the pumping lemma, we have to split strings into $uvwxy$ (for example). Say the language was $a^n$$b^n$$a^n$$b^n. We could it this way: a^r$$a^s$$a^t$$a^u$$b^n$$a^n$$b^n$, with $uvwx$ all ...
180 views

### Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :(