Questions tagged [regular-language]

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

Filter by
Sorted by
Tagged with
1
vote
1answer
11 views

Determine if complement of non-regular language is context-free

I'm trying to understand if the complement of non-regular language is context-free. for example: $L=\{ 0^n 1^n │ n\ge0 \}$, I need to prove that the complement of $L$ is regular so $L'$ is context-...
1
vote
2answers
39 views

What does w ∈ a, b* mean?

What does $w ∈ a, b^*$ mean? The context is the language of an automation, which is $L=\{w∈ a, b^*|:|w|$ is even and the central symbols of $w$ are $aa\}$ I really don't understand what $w ∈ a, b^*$ ...
0
votes
1answer
69 views

Regular expression that accept the language of all binary strings with exactly two $a$’s and at least one $b$.

I need to design a regular expression that accept the language of all binary strings with exactly two a’s and at least one b. Here's what I've got so far: $(aab^+) \cup (ab^+a) \cup (b^+aa) \cup (ab^+...
0
votes
1answer
28 views

Do DFA's with outputs not have a set of final states?

In Ullman's Introduction to Automata, Languages and Computation (1979): We formally denote a finite automaton by a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where $Q$ is a finite set of states, $\Sigma$ ...
0
votes
1answer
16 views

Is a right invariant equivalent relation necessarily $𝑅_𝑀$ for some finite automaton $𝑀$?

In Ullman's Introduction to Automata, Languages and Computation (1979) Let $M = (Q, \Sigma, \delta, q_0, F)$ be a DFA. Relation $R_M$ is defined as: for any $x$ and $y$ in $\Sigma^*$, let $xR_My$ if ...
1
vote
1answer
10 views

How to transform a regular expression into a context free grammar with 2 variables?

I'm tasked with transforming this regular expression $((0+1)(0+1)^*(0+1))^*$ into a context free grammar. As an added constraint I'm must do so with a maximum of 2 variables. This is what I did : <...
0
votes
0answers
18 views

Can the string matching problems in algorithm books be formulated in terms of regular expressions in formal languages?

I was wondering how to formulate the (sub)string matching problems in computer algorithm books in terms of regular expressions in formal languages? How is the problem of finding one match of a ...
0
votes
0answers
24 views

What is the terminology or concept related to a prefix of a string which is also its suffix?

What is the closest terminology or concepts and/or theorems in formal languages related to a nontrivial prefix of a string which is also its suffix, and the longest such prefix of the string? For ...
1
vote
1answer
56 views

Why can regular expressions be defined without mentioning closure under intersection with regular sets, homorphisms, and inverse of homomorphisms?

The family of regular sets is the smallest full trio (closed under intersection with regular sets, homomorphisms, and inverse of homomorphisms) and also the smallest full AFL (closed under union, ...
0
votes
1answer
62 views

What is a mathematically rigorous treatment of “sentences”, “words” and “language”?

How do mathematicians rigorously deal with words and sentences? In other words, how are words sentences constructed in a mathematical sense? Is there some (accepted) system for constructing words? I ...
1
vote
1answer
40 views

Is there a commonly used notion of regular language outside of finite order types and $\omega$?

There are correspondences between regular languages and finite automata, and $\omega$-regular languages and Buchi or Muller automata (as well as the characterisation in terms of the monadic second ...
1
vote
0answers
23 views

Is this automata correct for this regular laguage?

for L(ab*a) finite automata picture
0
votes
0answers
8 views

Valid NFA with minimum number of states for set {0, 1} where each 0 is followed by a 1

Construct a Non-deterministic Finite State Automaton (NFA) with minimum number of states for the set of strings over {0, 1} such that each 0 in the string is immediately followed by a 1. This is the ...
1
vote
1answer
26 views

Show that pda with limited stack accepts regular languages

So what I have to prove is that pushdown automaton with a limited stack size $k \in N > 0$ describes exactly the regular languages. [Edit:] I know that regular languages don't need any memory or ...
0
votes
1answer
20 views

Regular expression for languages with limit on repeated letters

I'm working through some mathematical Regex questions and I was wondering if you could review some of my answers. (1) L={w ∈ {0,1}* | w contains at least three repeated 1s} ...
0
votes
1answer
29 views

Regex with a limit on repeated letters

L={s ∈ {X, Y, Z, K}*|s doesn't include 5 consecutive Ks} How can I represent this in a regular expression? Specifically, how would I restrict the number of certain letter appearing repeatedly in a ...
0
votes
0answers
9 views

Regular language and Finite Automata (FA).

Consider the following FA Build a transition graph with only two states that accepts the same language as the FA. Build a FA which accepts the same language as the FA, but has fewer states. So ...
-1
votes
1answer
22 views

comeputer science myhill nerode equivalence class [closed]

hello people i am stuck with my tasks, i got problems with the task! Prove with myhill nerode criterium if a and b are regular or not? a) L 1 = {0w | w ∈ Σ ∗ } b) L 2 = {w0 | w ∈ Σ ∗ }
0
votes
0answers
19 views

Kleene closure of a disjunctive normal form for regular expressions

$\newcommand{\Kstar}[1]{#1^\ast}$ I would like to write the regular expression $$ a^\ast b^\ast + ( a + b )^\ast b a ( a + b )^\ast $$ as a Kleene closure of a union of catenations or in other words, ...
1
vote
1answer
23 views

Construct a Non-deterministic Finite State Automaton (NFA)

Construct a Non-deterministic Finite State Automaton (NFA) M with minimum number of states for the set of strings over {0, 1} such that each 0 in the string is immediately followed by a 1. The image ...
2
votes
2answers
59 views

Prove that, if languages $R$ and $S$ are boring, then so are $R\cup S$ and $R\cdot S$

This problem is adapted from "Mathematics for Computer Science" (Lehman, Leighton, Meyers, 2018). Can anyone verify my solution attempt? Problem A word is a finite sequence of $0$'s and $1$'...
1
vote
1answer
26 views

Automatic complexity of word problem

Suppose $L$ is a regular language. Let’s define its automatic complexity $ac(L)$ as the minimal possible number of states of a DFA, that recognizes $L$. Now, suppose $G$ is a finite group. $A \...
0
votes
0answers
28 views

Regular expression without subword 000 [duplicate]

what is the regular expression for the language above {0,1} that does not contain the subword 000? Thank you for your help!!
0
votes
1answer
38 views

Prove language of $0^n1^m$ is irregular for coprime $n,m$. [duplicate]

I need to prove that the language of $0^n1^m$ is irregular if $n$ and $m$ are coprime. (Or to disprove that) My attempt at this was to use the pumping lemma, and I've gotten $0^{n+(k-1)i}1^m$ after ...
1
vote
1answer
83 views

pumping lemma - union of regular languages

In the question, we have regular languages L1, L2 with the constant of the pumping lemma - n1,n2. Also, we have the language L = L1 + L2 with the constant n of the pumping lemma. I need to prove that ...
1
vote
2answers
39 views

union of regular language and non regular language

I have the languages $L_1 = 00^*\{1^n0^n \mid n \geqslant 0\}$ and $L_2 = 0^*1^*$. I know that $L_1$ is not regular and $L_2$ is. But is $L = L_1 + L_2$ is not regular? An extended explanation will ...
0
votes
2answers
29 views

How do these languages intersect the way they do?

So I have these languages: $$ \begin{split} A_1 &= \{w1^{|w|}|w \in \{0,1\}^*\} \\ A_2 &= \{ww|w\in\{0,1\}^*\} \\ A_3 &= A_1 \cap A_2 \end{split} $$ $A_1$ and $A_2$ are irregular but it ...
1
vote
2answers
18 views

Prove that a class of regular languages is closed under an operation

We define an operation addone on any string in $\Sigma^*$ that adds a $1$ after the leftmost bit if such a bit exists. For example, $\operatorname{addone}(010)$ is $0110$, $\operatorname{addone}(00)$ ...
0
votes
1answer
30 views

Why is the minimal pumping length for $(01)^*$ equal to 1?

I see why the minimum pumping length is at most 2 (since 01 can be pumped). But why is this counterexample not valid? Let $A=(01)^*$ and assume it has pumping lenght $p=1$. Then lets consider the ...
0
votes
0answers
37 views

Complexity of determining the Hamming distance from a given word to a given regular language

Suppose $L \subset A^*$ is a given regular language (defined by the corresponding DFA). What is the best possible computational complexity of an algorithm, that for a given word $w \in A^*$ returns ...
0
votes
1answer
62 views

Prove that if L is decidable then half(L) is decidable too

Let L be decidable language, and let half(L) be: half(L)={u∣uv∈L s.t.|u|=|v|}. Prove that if L is decidable then half(L) is decidable too. I tried to build a Turing Machine to decide half(L) but none ...
1
vote
0answers
20 views

Using induction to show that the languages $\mathcal L(A)$ and $\mathcal L(G(A))$ are the same

Let $\newcommand{\perm}[1]{\left\langle #1 \right\rangle}A = \perm{ Q, \Sigma, \delta, q_0, F }$ be a finite, nondeterministic automaton and $G(A) = \perm{ \Sigma, V, P, S }$ the grammar generated by ...
0
votes
1answer
29 views

How to prove that a language is not regular without the use of the Pumping Lemma?

I have an exercise to prove. Prove that $\{a ^ i b ^ j c ^ k \mid i, j, k \geqslant 0, \text{if $i = 1$ then $j = k$}\}$ is not a regular language but that respects the conditions of the Pumping ...
0
votes
1answer
27 views

Power of a group of languages

I need help finding and proving the power of the group of languages A: A={L|L=L* and L is over $\Sigma\ = \{1\}\ $} I was thinking of the fact that if L=L* - if $1^k\ ,1^p \in L $ then, m=k+p , $...
0
votes
0answers
32 views

What is the difference between pumping Lemma for regualar languages and pumping lemma for context free languages?

Is there a difference between the pumping lemma for regular languages and the context-free languages? I know that pumping lemma for context-free languages is a generalization of pumping lemma for ...
0
votes
0answers
46 views

Defining prefixes for regular expressions

When dealing with this question, I came to realize that I'm not sure how sensible it is to define prefixes for regular expressions. So far I've run into two sorts of prefix definitions, one for ...
2
votes
1answer
45 views

Showing that the language of prefixes $\operatorname{pre}\mathcal L$ is regular by using the definition of a regular language

A language is regular, if it is generated by a regular expression, meaning the expression consists of the alphabet $\Sigma_{\mathrm{RE}} = \Sigma \cup \{\epsilon, \varnothing, +,\ast,(, )\}$, and is ...
2
votes
1answer
71 views

Are regular expressions sets?

I have a confusion concerning regular expressions and languages generated by them. In our course material, regular expressions are defined as follows. If $\Sigma$ is an alphabet, regular ...
-2
votes
1answer
33 views

Prove $(L^*)^*=L^*$

https://i.stack.imgur.com/XJqT4.png How would I do this? I have tried to think of a solution but nothing comes to my mind.
0
votes
1answer
38 views

Why is $a^nb^n$ irregular but $a^*b^*$ regular?

I was reading to find how a subset of regular language can be irregular and came across this. This raised the question why is $L = \{a^nb^n:\, n > 0\}$ irregular but not $a^*b^*$ ? I understand a ...
0
votes
1answer
44 views

Is any anagram of the empty language the same as the empty language?

Given a regular expression r, r~ contains all anagrams of r. L(r) is the language accepting all words that can be constructed from r. E.g. Given the language L(r) = {dog}, L(r~) = {dog,god,odg,ogd,...
0
votes
1answer
28 views

Describing the language of a given DFA

I am do not see how I could find the regular expression of the language of the DFA below. It is clear that it has to look something like $$b \cup (a...)$$ but I do not see how to describe the "...
4
votes
1answer
38 views

How many total states do you need to prove that union of two regular languages also gives you a regular language?

I am reading a book called Introduction of the Theory of Computation. In the book, the author tries to proof $A_1 \cup A_2$ is regular if $A_1$ and $A_2$ are regular. He is using Proof by ...
2
votes
1answer
27 views

Automata, operation on languages

I have some exercise to solve for my automata course at university. I cannot understand, however, what exactly $L_1L_2$ means for some languages $L_1$ and $L_2$. The problem is - prove that If $L_1\...
1
vote
1answer
26 views

What does the “\” mean in this statement about regular languages?

I have having difficulty finding the meaning of the backslash in the statement. I don't know if it could be a division, an OR operator or something else. If someone could provide information about it, ...
0
votes
2answers
59 views

Proving: $\bigcup_{i=0}^{\infty}\{\epsilon\}=\{\epsilon\}$

During a test in Automata I had to prove that $L[(\epsilon)^*]=\{\epsilon\}$ for REs, where $\epsilon$ is the empty word. I didn't prove the following last step because I thought it was trivial: $$ \...
1
vote
2answers
52 views

Find a finite automata that recognizes $L=\{w\in\{0,1,2\}^*\mid\text{$w$ has one $1$ and odd number of $0$}\}$

Find a finite automata that recognizes $$L=\{w\in\{0,1,2\}^*\mid\text{$w$ has only one $1$ and odd number of $0$'s}\}.$$ I don't think it is possible to construct such automata, but I am not able to ...
0
votes
1answer
61 views

How can I concatenate these two DFA's?

Let the alphabet = {a, b} for $L_{1}$ and $L_{2}$ $L_{1}$ = { w | w contains an even number of a's } $L_{2}$ = {w | w has at least 1 b after each a } $\rule{10cm}{0.4pt}$ $\hspace{4cm}L_{1}$ $\rule{...
1
vote
1answer
30 views

Are all elementary equational languages regular?

Suppose $A$ is a finite alphabet. $x \notin A$. Let's call a word equation over $A$ a pair of words $(w, u) \in (A \cup {x})^* \times (A \cup {x})^*$. Let's call a word $\alpha \in A^*$ a solution of ...
0
votes
1answer
22 views

Why does a translated DFA usually not have $2^n$ states?

If we translate an NFA to a DFA, it can have $2^n$ states at the maximum. However, this usually does not happen? Why is that so and what is the condition such that the translated DFA will have $2^n$ ...

1
2 3 4 5
21