# Tagged Questions

35 views

### Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
23 views

### Why cant this be a Regular Language?

Given L - the language consisting of all the strings of the form $\{0^n 1 ^m\}$ where $m < n$ How can I prove that L is not a regular language?
17 views

### Hierarchy of hardness for the pumping lemma for regular languages.

Whenever I bring up the Pumping lemma for regular languages people often say `better to use the Myhill-Nerode theorem'. I want to make this thought rigorous. Def: A language $L$ is pumpable if there ...
53 views

### Prove that this language is not regular (Pumping Lemma)

Prove that the following language is not regular. I have no clue where to start. $$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$
56 views

### Prove the following by using mathematical induction

If we define the alphabet such that $$\Sigma = {\{a,b}\}$$ and let $w$ be a string over it. I'd like to prove $$( \operatorname{comp}(w))^R = \operatorname{comp}(w^R)$$ where $$w^R$$ and ...
52 views

### This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
71 views

### Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
18 views

### proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
76 views

### Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
41 views

### Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B$

Given $A,B$ regular languages. Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B$ Whereas $A\prec B$ stands for: $A\subset B$ and $B\setminus A$ is infinite regular language. I ...
47 views

### Proving that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular. [duplicate]

I am trying to prove that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular, whereas: $\Sigma=\{a,b\}$. I tried to use the pumping lemma with no success. I have also tried to ...
91 views

### Turing Machine for comparing, copying, and operating

If one wants to design a Turing Machine for a function such as this: Where $x>0,y>0$ and are both integers represented in unary, so an example movement in this TM on the read-write head would ...
45 views

### Find Regular Grammar from NFA

I'm currently doing some self study to improve my half-forgotten college theory of comp skills. I'm going over some problems from an old book and it asks you to find a regular grammar for the ...
57 views

### Working with the word w⋅y, while given the word y⋅w

$L$ is a regular language. I am given $F(L)$ such that $$F(L)= \{wy \mid yw\in L\}$$ I need to prove that if $L$ belongs to $L_\text{dfa}$, $F(L)$ also belongs to $L_\text{dfa}$. I am having a hard ...
47 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 ...
205 views

### Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
113 views

### Number of states required to recognize $\{ ss : s \in \{ 0 , 1 \}^*, |s| = i \}$ and its complement

$$\Sigma = \{0,1\}\;\\ S_{i} = \left\{ss: s\in {\Sigma}^{*} \text{and s has length i}\right\}$$ Prove that for any $i$, any DFA recognizing $S_{i}$ must have $2^{i}$ or more states. Design a ...
285 views

### Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
37 views

### Regular Functional Algorithms

A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems. Definition: A functional read-only ...
83 views

### Prove that $\{1, 11, 1001,\dots\}$ is an irregular language

Let $L:=\{1, 11, 1001,\dots\}$ be the language with alphabet $\{0,1\}$ which is formed by all powers $3^n, n=0,1,\dots$ written in binary notation. How to prove that $L$ is not regular?
85 views

### Give a regular grammar for L

Give a regular grammar for L= {a^n b^n : n<=100} I would do something like this : S---> A | empty string A---> aB| empty String B---> Ab but How do we keep count of the number in the grammar? ...
43 views

### If $\{w^k|w\in L\}$ regular implies L regular?

If L is a language and the language $$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$ is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence) We came across this question when ...
114 views

### Pumping Lemma problem

Apply pumping lemma to each of these and prove that they are not regular. $L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$ $L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$ Here my ...
80 views

### Is there a problem with this example?

In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
348 views

### Question about regular languages and finite automata

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
105 views

### Language over $\{0,1\}$

I am learning about languages but struggling with operations on them. In my book there are some simple examples but how would I for example describe a language over $\Sigma=\{0,1\}$ such that every ...
910 views

126 views

### Showing $L=\{uw \mid \exists v:uv\in L_{1},vw\in L_{2}\}$ is regular

Let $L_{1,}L_{2}$ be regular languages and define $L:=\{uw \mid \exists v\in\Sigma^{*}:uv\in L_{1},vw\in L_{2}\}$. I wish to prove that $L$ is regular using only closure properties (such as ...
312 views

### A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
239 views

### How to draw this finite state automaton?

I know that the following language $L$ = {$a^n$ where $n$ is a prime number bounded by some fixed $f$} is a regular language because it is finite. Because it's a regular language, I should be able to ...
72 views

### Regular expression arithmetics

What are the rules of regular expression arithmetics ? For example: Let $\Sigma=\{0,1\}$ $1. 1+01=(\epsilon+0)1$. $2. (\epsilon+00)^*=(00)^*$
778 views

### Why isn't this a regular language?

I'm stuck as to figuring out why $L_1$={$n^p$ | $p$ = a prime number} is not a regular language but $L_2$={$n^p$ | $p$ = a prime number bounded by some fixed number f} is. I can see that $L_2$ is a ...
204 views

### Using the pumping lemma to show that a language is not regular (Computer Science)

Show that $L=\{a^{n^2} | n \ge 0\}$ is not regular Hey guys. I'm taking a CS class and this stuff is really new to me so bear with me. I tried to look if I get some contradiction by using the ...
### $\{\langle M,q,x\rangle$| $M$ is a Turing machine and $q$ is a state of M and running of $M$ on $w$ visits $q\} \notin R$?
I'm trying to find where does the language $\{\langle M,q,x\rangle$| $M$ is a Turingmachine and $q$ is a state of M and running of $M$ on $w$ passes on $q\}$ belong? whether it's $R,RE$ or none of ...