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
187 views

Regular languages closed under prefix operation

Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$\mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \}$$ ...
87 views

Pumping Lemma Proof (Type of wcw language)

I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma. The structure of the language i think can be explained ...
377 views

Constructing a NFA from a regular expression

I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression. I started by constructing the NFA ...
64 views

How to prove the class of regular languages is closed under 3MAJ?

Let $\Sigma$ be some alphabet. We define the following operation on the set of all languages over $\Sigma$. The operation $\mathrm{3MAJ}(L_1, L_2, L_3)$ takes in three languages $L_1$, $L_2$ and $L_3$ ...
97 views

21 views

If L is a regular language, then the particular L′ is also regular? [duplicate]

Show that if $L ⊆ Σ^∗$ is a regular language then the following language is also regular: $$L' = \{w\mid ∃x, y ∈ Σ^∗ : w = xy ∧ yx ∈ L\}$$ Can you give me a hint how to solve that?
15 views

LL(1) Eliminate Ambiguous ε-derivations

I have this grammar I want to convert to LL(1): S -> A B a | A B b A -> A c | B d B -> A a | b I eliminated the left-recursions, I factored out the ...
26 views

How does a transition function behave in a FSM when an input is not recognized (i.e. the input is not contained in the alphabet)?

In Sipser's Introduction to the Theory of Computation, the provided proof for the union operation being closed for regular languages has a step for the transition function that I find a bit lacking. ...
34 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 ...
75 views

48 views

Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular

I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it ...
57 views

Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$

how can I find the regular expression for this intersection ? I've tried to find words but it did not help too much.. $$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$
62 views

Intuition for irregular languages

I'm struggling in understanding how to recognize irregular languages. I know what the meaning of irregular language but still find it hard to recognize. Are there any tips to recognize better and to ...
61 views

All strings in which every substring 000 appears after every 1

I found this given problem as follows: Write a regular expression where all strings in which every substring 000 appears after every 1. Now, I also found the answer from Illinois university study ...
112 views

Formal Binary String Regular Expression (each pair of 00 must have 11 before it)

I'm trying to construct a regular expression for the language of binary strings in which every 00 must have at least two 1s before it. I realize this can be done with lookbehinds using the following ...
36 views

Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?

In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the ...
128 views

Can you reduce every decidable language to a regular language?

One of my previous questions on an exam was the following Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language). If so, does this mean that ...
45 views

Finite languages $L\in RE$

I want to check if I understood it in the right way. In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn'...
77 views

Proving that a certain language is regular using pumping lemma

Let $\Sigma = \{a,b,c,\ldots,x,y,z\}$ be the Latin alphabet, consisting of 26 letters. Consider the language $L$ of all words $\alpha$ over $\Sigma$ satisfying the following constraints: If $\alpha$ ...
37 views

Unique decipherability of infinite regular language

Can we design an algorithm to test if a infinite regular language is a code? We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular ...
17 views

Check if the regular expression r made up of the single symbol alphabet Σ = {a} defines language L(r) = a* [duplicate]

I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $\Sigma = \{ a \}$ and check if the regular expression $r$ ...
51 views