Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [regular-languages]

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

2
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
0answers
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}∗...
-1
votes
1answer
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$$ ...
0
votes
0answers
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 ...
-1
votes
1answer
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\}$
1
vote
2answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
38 views

Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms

I want to prove that $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ is not always true. If $L_1 = (ab)^*$ and $L_2 = (ba)^*$ with mapping $H(a) = 1$ and $H(b) = 1$, $H(\epsilon) = 2$, then $H(L_1 \cap L_2) = ...
1
vote
1answer
59 views

Not able to prove non regularity using pumping lemma

$L$ = $0^p1^q0^p$. Where $p, q \geq 0$ Here for any string $w \in L$ , I can have $u$=$0^p$, $x$ = $1^q$ and $v$= $0^p$ and $x^i$ will belong to L for all $i \geq 0$ So how do I prove it to be non ...
2
votes
0answers
73 views

How to prove that a language created from a context-free gramar's left side is regular(or left-linear)?

Given a context-free grammar $G$, let $\longrightarrow_G$ be the (one-step) rightmost derivation relation, and $\longrightarrow^*_G$ its reflexive and transitive closure. Let $S$ be the start symbol ...
0
votes
0answers
116 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 ...
1
vote
1answer
139 views

Difference between NFA and NBA

NFA (nondeterministic finite automata) accepts only finite words while a NBA (nondeterministic Büchi automata) accepts infinite words (and hence $\omega-$regular languages). I think the example ...
7
votes
2answers
640 views

Is there an analog of “regular” for infinite strings?

Consider the sequence $s_1 = (1, 0, 1, 0,\dots)$. It seems "regular" in a way that, e.g. $s_2 = (1, 2, 3, 4,\dots)$ is not. I'm not sure how to formalize this intuition though. One thing which jumps ...
2
votes
1answer
57 views

Is there any difference between these two languages?

If I have the following two languages: $L_1= \{ w \in \{a,b\} |$ $w$ has neither $ab$ nor $ba$ as a subword$\}$ $L_2= \{ w \in \{a,b\}^* |$ $w$ has neither $ab$ nor $ba$ as a subword$\}$. Is there ...
0
votes
1answer
796 views

Regular expression for the language containing neither aa nor bb

I want to create a regular expression for the language $L=\{ w \in \{a,b\} |$ w has neither aa nor bb as a subword$\}$. I've tried various things, but I can't seem to get the correct regular ...
0
votes
0answers
56 views

Show that this language is not regular by Pumping Lemma

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 ...
1
vote
0answers
45 views

Finding language family of given language

I came across following problem: Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any language, then what is the smallest language family $L'$ belongs ...
1
vote
0answers
67 views

Is universality problem of single state NPDA decidable?

I came across following problem: Given single state non deterministic pushdown automata $M$, whether $L(M)=\Sigma^*$ is decidable? Now I know for DPDA/DCFG/DCFL, universality problem is ...
1
vote
1answer
194 views

Whether equivalence of different types of automata is of P-type?

I came across following problem: Which of the following problems is/are P-problems? (I) Equivalence of DFA's (II) Equivalence of NFA (III) Equivalence of regular expressions Now I know I ...
3
votes
1answer
487 views

Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$

I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states. However recently came across following text: ...
2
votes
1answer
64 views

Intersection of languages using closure properties

$L_1 \in \mathrm{CFL} \cap L_2\in \mathrm{CSL}$ is $\mathrm{CSL}$ because every $\mathrm{CFL}$ is $\mathrm{CSL}$ and by applying closure property of $\mathrm{CSL}$ under intersection, it's $\mathrm{...
0
votes
1answer
160 views

Pumping-Lemma regular languages: Consider multiple cases?

The language $ L = \{ a^nb^mc^m : n,m \in \mathbb{N} \} $ is non regular. Suppose this needs to be proven using the pumping lemma for regular languages: Be $ z = ab^nc^n $ such that $ z=uvw, |v| \geq ...
4
votes
2answers
339 views

Does closure under union and concatenation imply closure under Kleene star? [duplicate]

For decidable languages (or a particular subset of decidable languages, e.g., regular, context free) does closure under Kleene star follow from the proof of closure under union and concatenation? The ...
2
votes
2answers
697 views

Use the pumping lemma to show the language is not regular

I can use the pumping lemma to prove simpler examples, but i'm finding this problem rather complex partly due to the notation. Can anyone explain how I would do this problem: For any string $s$ in ...
2
votes
2answers
96 views

Recursive definition of a language $ L $ over $ \{a,b\} $

How would I start the recursive definition of the following language: L over {a, b} such that L consists of strings in which each occurrence of b is immediately preceded and followed by an a The ...
0
votes
1answer
75 views

Prove this language is non-regular [duplicate]

I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated. Prove using the Pumping Lemma that the following language is not ...
3
votes
1answer
104 views

Is a language containing set of binary numbers which are divisible by number N Regular?

Let N be any positive integer, then is following language regular for every $N$? $L$ = { $B_n : B_n(modN) == 0$ } where $B_n$ is binary representation of a number. E.g, $L=\lbrace B_n : B_nmod31 ==...
1
vote
2answers
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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, ...
1
vote
1answer
208 views

Tokenization Problem

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult. My Regular ...
0
votes
0answers
56 views

Empty words in regular languages

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 \...
5
votes
2answers
713 views

How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?

Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie completely inside CFL. So, as regular set is completely inside CFL set, their ...
1
vote
1answer
58 views

How to find a regular expression

I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules? For example, for the language $L \subset \{ a,b\}^* $ which ...
0
votes
2answers
386 views

Infinite union of regular language

Deciding if the infinite union of a set of regular languages is regular is undecidable. By closure property of regular languages, regular language is not closed under infinite union so is the above ...
1
vote
1answer
64 views

Prove correctness of this (context-free) grammar

I created a context free grammar for the language which has words where twice as many a than b occur. So as example, the ...
-1
votes
1answer
76 views

is it possible to do a DFA for these languages? [duplicate]

I have just started learning Automata Theory, so far I only know about regular languages, FSM (NFAs and DFAs) and regular grammars, but I come across a question like this: "Given the next languages, ...
0
votes
1answer
663 views

What is the meaning of a prefix-free language?

Tried a bunch of resources to read about it, still don't really get it. This is what Wikipedia says A prefix code is a type of code system (typically a variable-length code) distinguished by its ...
0
votes
1answer
179 views

Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode

Consider the alphabet $Σ = \{1, +, =\}$ and the following language, $PLUS = \{ 1^m + 1^n = 1^{m+n} \mid m, n ∈ ℕ \}$. Prove with Myhill-Nerode that PLUS is not a regular language. I know how I ...
0
votes
0answers
33 views

Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness. Where ...
0
votes
1answer
502 views

Construct an equivalent NFA for the given regular grammar

Given is the regular grammar G = ({A,B}, {a,b}, P, A) with the rules P : A → aB, a, ε (where ε is the empty word) B → bA, b ...
1
vote
1answer
459 views

Minimum pumping length of regular language

I know the method to the find the minimum pumping length of regular language by constructing minimal DFA and finding the number of states but I am not able to quite understand why is it working. For ...
1
vote
1answer
18 views

Comparing the closed behaviors corresponding to finite state automata

Let $G$ be a finite state automaton (FSA) with transfer function $\delta(\cdot,\cdot)$ and initial state $q_0$. Suppose also $\Sigma_{G}$ represents its alphabet. Assume that its closed behavior is a ...
1
vote
1answer
497 views

How to find the equivalence classes of a regular language

Given a language $L=\{ 0^m1^n | m \neq n \}$ over $\Sigma = \{ 0,1 \}$, how would one go about characterizing the equivalence classes of this language? I know there isn't a formal algorithm for that, ...