Questions tagged [regular-languages]

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

1,099 questions
50 views

Can three regular languages be concatenated?

I can't seem to find anything about this and I wonder if I'm asking a silly question. If you have three languages $L_1=\{a,b\}, L_2=\{c,d\}, L_3 =\{e,f\}$, can they be concatenated? If yes, would ...
130 views

How to prove that a transformed language is regular using an NFA

I am trying to prove that if a language $L$ of binary strings (i.e. a subset of [01]*) is regular then so is the transformed language $plus (L)$ consisting of ...
163 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}∗...
41 views

Regular Expression Building

I'm having trouble constructing a regular expression to meet the following criteria: $$\sum = \{0,1\}$$ $$\epsilon \in L$$ $$0 \in L$$ $$1 \in L$$ $$\forall x \in L, 110x \in L \land x01 \in L$$ ...
83 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 ...
49 views

Prove EXP to be regular or non-regular [duplicate]

Given L is regular, Prove/Disprove that the following language is regular or not. $EXP = \{w| w^{|w|} ∈L\}$
78 views

Does this proof work for infinite regular languages

My proof was deemed false because it does not work for infinite regular languages, but I don't understand why. Prove: "If we remove one string from any nonempty regular set, the resulting set is ...
115 views

Proving that $L = \{ a^{n!} \ | \ n \geq 0 \}$ is not regular

Let $L$ a language over $X = \{a\}$ defined as follow : $$L = \{ a^{n!} \ | \ n \geq 0 \}$$ I want to prove that $L$ isn't regular, I have searched in the forum for an equivalent question, but I ...
10 views

Choose a specific regular language to prove a language is not regular [duplicate]

I've tried a few tricky languages such as D = { w | w has an equal number of occurences of 01 and 10 as substrings} but I don't have the means to prove this one as being not regular (and I cannot ...
58 views

Set of infinite DFA's

$INFINITE_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\}$ Here $(A)$ denotes the encoding of DFA Is above language regular, CFL or recursive ? I know that ...
590 views

How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent

Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form: To a regular expression equivalent. What I have tried was using arden's rule. However I ...
36 views

Is DCFL closed under union with RL? [duplicate]

So i know that DCFL is not closed under union, but what about union with RL? Because what if both of the languages can start with the same string?then when we are building the DPDA for the union and ...
38 views

160 views

1k views

Decidability of whether a language described by Turing machine is regular

I am trying to prove decidability of problem whether language described by Turing machine is regular. My idea is that I can simulate finite automaton with a subset of Turing machine instructions, ...
41 views

Finding whether the language is CFL or regular

$L = (0^i 1)^n$ where i=1,2,3,4...n and n>=0 For eg :- 00010001 doesn't belong to the language as n=2 but i=3 at the beginning. 001001001 belongs to L as n=3 and i=2 in all cases. I know the ...
302 views

Intersection between regular language and context-free language [closed]

In general, context-free algorithm are not closed under intersection but the intersection between a regular language and a CF language is known to be context-free. My question is: does exist an ...
1k views

Decide whether the Language is regular {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0} [duplicate]

how would you prove if this language is regular/irregular? question given: Decide for each of the following languages whether it is regular. If so, design a DFA/NFA for recognizing it, and if not, ...