# Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

132 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
39 views

### Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws

I tried to prove this by starting at RHS: $$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$ But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful. Any ideas?
38 views

87 views

### Prove that all regular language is in L

im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space). I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all ...
42 views

### Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
342 views

### Is the set of strings with equal number of 010’s and 101’s regular?

Consider the language $$L = \{ w\in \{ 0, 1\}^*: \#_{010}(w) = \#_{101}(w) \}$$ Is $L$ is regular? If it is not regular, can we prove that using the pumping lemma (only with pumping down)?
46 views

### Is this proof for pumping lemma legit?

Prove that $L=\{a^{n}b^{m}c^{k}\mid n\leq(m+k)\}$ is not regular. I used the pumping lemma as follow: there exists $n\in \mathbb{N}$ $z=uvw$ $|uv|\leq n , |v|\geq1$ $uv^iw$ is a string in L, so ...
343 views

### Strings that do not contain 11 as a substring

Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring. She wrote ...
102 views

24 views

### Is there any algorithmic way to decide the equivalence classes in the nerode relation?

Consider the language $L= \{ x\in \{0,1\}^* |x$ ends with $00 \}$ The Nerode relation $R_L$ says $xR_Ly \iff \forall z\in \Sigma^*:xz\in L\iff yz\in L$ By looking at the language : I can conclude ...
157 views

### Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?

I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free ...
363 views

### Operations on regular languages

I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language ...
473 views

### Closure under swap operator

I am stuck on this problem and unsure how to proceed. I understand how to show that two languages are closed under regular operators, but not one like the 'swap' operator. Let swap : {a, b}∗ → {a, b}∗...
176 views

### Tool for NFA/DFA manipulation

I am look for a tool with any or all of the following features: Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams NFA to DFA converter NFA minimization NFA ...
325 views

### Computing substring language on automata

Given a DFA, it is possible to compute the automaton that recognizes the language of its substrings (you can compute it as the automaton that recognizes the suffixes of its prefixes). I would like to ...
Over the alphabet $\Sigma=\{a,b\}$, we define $$L=\{a^pb^m: p\text{ is prime }, m>0\}+\{a^r:r\geq 0\}.$$ I must show that this laguage is not regular using the pumping lemma. I guess I should ...
Let $L_1,L_2$ be any $\Sigma$-Languages, with $l_1\in L_1, l_2\in L_2$ If I have a regular Language $L(l_1(l_2l_1)^*l_2)$ would the word $\omega=l_2$ be recognized? I'm confused because if \$\epsilon \...