# Questions tagged [regular-languages]

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

1,607 questions
Filter by
Sorted by
Tagged with
15 views

### A regular expression E* defines an infinite language $L_E$ [closed]

So I'm studying for an exam which is about languages and automata. There is a question in the book which asks us to prove that given a regular expression that can be infinite, say $E*$, the language ...
16 views

### Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$

Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$. Hello, I have been trying to solve this problem, my intuition tells that ...
25 views

### Which z should I pick?

I'm currently trying to show that the language $L_2=\{0^n \text{ } | \text{ } n=2^k, k\geq 0\}$ is not regular by using the Pumping Lemma (at least I think it is not regular, because I couldn't find ...
32 views

### Show that if L is CFL and R is a regular language then {w ∈ Σ^∗ | xw ∈ L for some x ∈ R} is context free

Show that if $L$ is CFL and $R$ is a regular language such that they both share the same input alphabet $\Sigma$, then $C = \{w \in \Sigma^*\mid xw \in L$ for some $x \in R\}$ is context free. Hi I'...
8 views

### Contiguous-substring operator

If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
94 views

### Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$

Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma. I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is ...
98 views

### Create a Deterministic Finite Automaton for a regular expression

I want to create a finite state machine that accepts the following language: $$L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}$$ So I began by writing a regular expression ...
43 views

### Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular

I want to understand how is this proof working. What I know: Pumping lemma for regular language-: Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for every ...
62 views

### $\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma

As I am currently teaching regular languages and pumping lemma, I was searching for nice examples of languages, regular or not, for exercises. $L_1 = \{vv\mid v\in \Sigma^*\}$ is a classic example, ...
93 views

### Build PDA for a language with unknown input alphabet

$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows: $L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$ In this exersice I am not given any ...
45 views

### Describing the language of this Automaton

I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. ...
206 views

### building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

$\{a^p; p$ is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$ I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ ...
51 views

### Irregularity of $\{a^p : p \text{ prime}\}$ using Myhill–Nerode

Consider the language $$L = \{2^k : k \text{ is prime}\}.$$ This language contains, for example, $2^3=222$, $2^5=22222$, $2^7=2222222$, and so on. I know that $L$ is irregular and so there must ...
56 views

### Size of minimal DFA

Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
78 views

### Are regular grammar languages defined from "accepting" states?

In a transition diagram, the language L(D) where D is the diagram is defined as all the words that are formed from following an "accepting" walk. Does the same apply for languages of regular ...
16 views

### Could I have used PL directly on this language instead of proving it the way I did? [duplicate]

In an exercise I'm trying to solve I have to say whether a language is regular or not. One of the languages is $L_1=\{0^i1^j \mid i,j \geq 1\text{ and } i\neq j\}$. I have already solved this by ...
52 views

### Check Proof Using Pumping Lemma to Show Language Not Regular

Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular. I'll state the pumping lemma here for clarity: Pumping lemma If $A$ is a regular ...
76 views

### Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language

I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
26 views

### Empty string in an ambiguous grammar?

I'm a bit confused by the role of the empty string in this ambiguous grammar: A' -> A A -> if A B A -> null B -> [empty string] B -> else S So what ...
Use Nerode's theorem to prove that the following language $L$ is not regular: $$L=\{a^{k!} \mid 1\leq k\}$$ Here is my attempt: Let $A$ be an infinte set of words s.t- $$A=\{a^n \mid n\in \mathbb{... 1answer 31 views ### Problem with Understanding Pumping Lemma I'm trying to solve this exercise that asks to determine whether a language is regular or not. Following the flow of the course I figured that the exercise is a test for Pumping Lemma application. But ... 0answers 26 views ### PDAs with bounded stacks accept regular languages [duplicate] I've been trying to solve the following problem from Martin's Introduction to languages and the theory of computation, 4th edition: Suppose that L \subset \Sigma^{*} is accepted by a PDA M. ... 1answer 60 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 ... 1answer 47 views ### Is the right quotient of a regular language respect to another regular language a regular language? Will the language \{w\in L_1\mid \exists v, wv\in L_2\} be regular if L_1 and L_2 regular languages? 1answer 888 views ### Determine if an NFA accepts infinite language in polynomial time Question Statement: Given a NFA N, design an algorithm that runs in polynomial time such that it determines if L(N) is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,... 1answer 57 views ### I want to determine if this language is non regular-any tips? After working through some examples of proving the non-regularity of languages I encountered this language$$ L = \{(ab)^{i}a^{j} | i \geq j, i,j \in \mathbb{N}\} $$Where a^{k} = a repeated k times.... 1answer 47 views ### How to design PDA for this language? I'm having a hard time trying to build the PDA for this language:$$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$I don't know how many a's should I push into the stack when reading a, and how many a's... 1answer 22 views ### How to show closure of regular languages without DFA,NFA,reg expressions Given a \Sigma I define a regular language as one of the folllows: \emptyset \left\{ \sigma \right\} for any \sigma \in \Sigma L_1 \cup L_2 for regular L_1, L_2 L_1 \cdot L_2  for ... 1answer 37 views ### The Closure Of Regular Language Under Reordering Alphabets For a regular language A with the alphabet \{a, b\}. Is L a regular language, where L contains strings of A but sorted with a and b? In other words, formula: L = \{ a^{\#_a(x)}b^{\#_b(x)... 1answer 74 views ### Simplify R:=0^*+0^*1\left(1+000^*1\right)^*0^* I'm trying to simplify the following REGEX:$$R:=0^*+0^*1\left(1+000^*1\right)^*0^*$$R is the result of transforming a GNFA that recognizes L:= \{w \in \{0,1\}^* | \left(\forall \ i \in \left[1,|w|... 1answer 263 views ### Converting DFA to Regular Expression Using State Removal I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression aa^*bb^*. As far as I can tell, this doesn't seem correct but I've been ... 1answer 51 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? 0answers 60 views ### Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs? This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ... 1answer 42 views ### Is the language L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \} regular or not regular? I'm trying to understand how to prove a language is regular or not regular, for example this language:$$L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$$Is this language regular or not? My solution Using ... 2answers 45 views ### Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular [duplicate] I have a computer science question: Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular These are all the facts I have been able to gather ... 1answer 68 views ### Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step ... 1answer 33 views ### Can any language be expressed by regular expression? I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression. In my current understanding the rule is &... 0answers 131 views ### Proving that a specific Turing machine accepts a regular language Calling all math buffs! ;) A Turing machine has two states - one accepting and one non-accepting. Furthermore, the Turing machine cannot overwrite blank symbols. (Note: It's assumed that the blank ... 1answer 61 views ### Prove language is not Turing-recognizable using contradiction Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable. Note: Prove by contradiction. No need for reduction. This is the problem I am trying to ... 1answer 22 views ### Can a non-regular language have a regular grammar? Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now: S -> 1 | 0 | ε Since it ... 3answers 91 views ### PDA for a language where the second part is not the reverse of the first part I came across an exercise for constructing a PDA for the following language:$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.Where L \subseteq ({a,b,c})^* So n and m are both a ... 3answers 233 views ### Can the diagonal language be empty? We defined the diagonal language as follows in the lecture: \begin{align*} L_{\text{diag}}=\left\{w \in \left\{0, 1\right\} ^{*}\mid w=w_{i} \text{ for some }i \in \mathbb{N} \text{ and }M_{i} \text{ ... 6answers 6k views ### Can regular languages be Turing complete? I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-... 2answers 578 views ### Regular Expressions - What is difference between a+ and a⁺ I'm very confused as to if a+ and a⁺ mean the same thing or are completely different. 1answer 33 views ### Regular expression for set of all strings containing no 3 consecutive 0s? The answer is 1^*01^*01^*+1^*(0+00+\in)1^* If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ... 1answer 51 views ### Prove that \{xyz \mid zyx \in A \} is regular if A is regular Does the following work and is there anything possibly simpler? Let X = (Q, \Sigma, \delta, s, F) be a DFA for A. Intuitively, we want to "remember" (or guess) two states p and q ... 1answer 50 views ### Dividing a String According to the Pumping Lemma I have some questions about how a string can be divided into pieces according to the pumping lemma. I am learning from Michael Sipser’s book Introduction to the Theory of Computation, 3rd Edition. He ... 0answers 33 views ### Summary of Pumping Lemma Application For my own understanding I would like to summarize how to use the pumping lemma to show that a language is not regular. The pumping lemma is defined as follows. Pumping lemma If A is a regular ... 1answer 44 views ### Need help with constructing a DFA I am trying to construct the DFA that accepts the following language L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \...
Let $𝚺$ be any alphabet and let $𝑳_𝟏 \subseteq 𝚺^{∗}$ and $𝑳_2 \subseteq 𝚺^{∗}$ be two non-empty languages. a. If $𝑳_𝟏 𝚺^{∗} \neq 𝚺^{∗}$ than what can we say about $L_1$. b.Let \$\Lambda \...