Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,599
questions
-1
votes
0answers
17 views
Show that L(P) is a regular language by constructing a FSM M such the L(M) = L(P)
I am practicing random CFG problems. I have the following problem which is very confusing for me. Can somebody help me on how to approach this problem.
Let $P = (K,\Sigma,\{\}, q_0,\Delta, F)$ be a ...
0
votes
1answer
32 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$...
-1
votes
0answers
18 views
Mealy Machine That Doubles a Binary
So I was trying to do a mealy machine that doubles a binary. But you know if you want to double a binary, you shift it to left once or add zero at the end. So this image is the one that divides by 2 ...
-3
votes
0answers
10 views
Finding out the language generated by a context-free grammar
how can i find out the language that accepted by this cfg :
S -> A B | B C
A -> B A | x
B -> C C | y
C -> A D | x
D -> y
1
vote
0answers
52 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 ...
0
votes
1answer
39 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 ...
1
vote
2answers
36 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 ...
0
votes
1answer
26 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 &...
2
votes
0answers
110 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 ...
0
votes
1answer
23 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 ...
0
votes
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 ...
0
votes
3answers
227 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{
...
0
votes
1answer
23 views
Understanding about pumping lemma for regular language-confusions of beginner-:
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 ...
-2
votes
0answers
52 views
Regular grammar for language that does not contain "abab"
I tried this :
$V = \{S,A,B\}$ and $T = \{a,b\}$.
$S \rightarrow aS | \epsilon | abaAS | BS$
$A \rightarrow a | aA$
$B \rightarrow bB | \epsilon$
Any thoughts/objections?
1
vote
1answer
29 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 ...
0
votes
2answers
42 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 ...
3
votes
2answers
562 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.
0
votes
1answer
49 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$ ...
-2
votes
0answers
16 views
How to choose splits in pumping lemma to prove language not regular
I am confused how we choose $0\;^{n-p}$ 1 and $0^n$ What's the logic going on here?
1
vote
1answer
40 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 ...
2
votes
0answers
32 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 ...
0
votes
1answer
43 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 \...
1
vote
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 ...
1
vote
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)...
-2
votes
2answers
61 views
Prove that the class of regular languages is closed under three operation
We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
0
votes
1answer
38 views
Prove the class of regular languages is closed or not closed under the operations below
Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
0
votes
1answer
41 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 ...
-1
votes
1answer
62 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 ...
1
vote
2answers
37 views
What is the minimum pumping lemma length of $01^*0^*1$?
I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$:
Set a PL. I chose $p=2$
Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
0
votes
2answers
62 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 ...
0
votes
0answers
47 views
If $L$ is regular, is $L/w = \{x\mid wx\in L\}$ regular?
I'm trying to see if the language $L/w = \{x\mid wx\in L\}$ is regular given that $L$ itself is regular.
It seems to me that if $L=L(A)$ for the NFA $A = (Q, \Sigma, \delta, S, F)$, then the NFA $A'$ ...
2
votes
2answers
57 views
If L is regular so is the language of compressed doubles
Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that
$$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$
I thought I could take a DFA which computes ...
1
vote
1answer
24 views
Regular expression for all a* except aa?
I'm stumped on how you would describe a language which is a* except for aa, so the following is acceptable:
a
aaa
aaaa
aaaaa
...
It's for part of the below DFA
0
votes
0answers
50 views
Whether $L(G)=L(R)$ is decidable for DCFL and CFL?
Let $G_1$ be the context free grammar and $R$ be regular language. Now I have to check whether $L(G_1)=L(R)$ is decidable or not?
My approach $\overline{L(G_1)}=\overline{L(R)}$. Now $L(G_1)$ not ...
0
votes
2answers
135 views
Regularity of CFG and DCFL
I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$.
My ...
1
vote
1answer
62 views
Why equality is decidable for regular language but not for $CFL?$
There are infinitely many different $PDAs$ for the same $CFL$ exist, therefore we can't check equality for $CFL.$
But also there are infinitely many different $DFA$ exists for same regular language. ...
0
votes
1answer
46 views
Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$ [closed]
We know that any languages $\subseteq\\\\$ $\Sigma^{*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{*}}$ which doesn't $\subsetneq\\\\...
1
vote
1answer
144 views
Adding a finite set to a non-regular language
Suppose $A = \{0^{n}1^{n} \mid n \ge0\}$, which is not regular, and let $B$ be a finite subset of $\Sigma^* \setminus A$. Is $A \cup B$ regular?
1
vote
1answer
51 views
Difference between (0)* and (0*)*
I know that,
0* generates, NULL, 0, 00, 000, 0000, ... and so on.
But how does (0*)* ...
0
votes
1answer
48 views
How to convert this regular grammar into a finite state automaton?
In a French course (p. 13) there is a language of words of {a,b,c} containing at least one occurrence of the string bac.
The ...
1
vote
1answer
23 views
Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?
I have a question that says that the complement of a regular language given as:
$L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
1
vote
2answers
40 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 ...
0
votes
0answers
35 views
Prove that the language such that the concatenation of any string with its complement is accepted by a regular language is regular [duplicate]
I’m trying to solve the following question: Suppose you have a regular language L with the alphabet {0,1}*. Show the language L’ = {x : x x_c \in L} is also regular. x_c is the flipped version of x ...
4
votes
2answers
74 views
Is the language "substrings of a regular language that are over half the length of the superstring" regular?
We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular?
I was provided the ...
1
vote
1answer
72 views
I have found an example where regular expression is not closed under concatenation. Where am I wrong?
$a^n$ is a regular expression.
$b^n$ is a regular expression.
their concatenation is $a^nb^n$ which is not a regular expression.
0
votes
1answer
46 views
Simplifying the Language of this DFA
Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
2
votes
1answer
56 views
Implication of the Pumping lemma
I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
1
vote
2answers
63 views
Can a non-deterministic finite automaton die out before reading the entire string?
I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by:
However, my problem is:
If the ...
2
votes
2answers
120 views
Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $
I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
1
vote
0answers
88 views
Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states
Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...
