New answers tagged regular-languages
3
votes
Accepted
DFA and NFA with 2 Substrings
Find an automaton for $L_1= \{uopv\mid u,v\in \Sigma^*\}$ and an automaton for $L_2 = \{upqv\mid u,v\in\Sigma^*\}$ (this should be easy enough).
Then, you can compute the product automaton of the two ...
- 7,092
2
votes
Exotic closure of regular languages
Because of the choices for $w_i$, it is easier to track the conditions if we include non-determinism.
Let $L_1$ be accepted by DFA $D=(Q, \{0,1\}, \delta, q_0, F)$.
Let NFA $N=(Q\sqcup Q_\#\sqcup\{\...
- 34.1k
0
votes
Prove that $\texttt{prefix}(L)$ is regular
The language $\textrm{prefix}(L) = \{0^n1^m:n \geq m\}$. It's not regular.
From the pumping lemma:
Let $L$ be a regular language. Then there exists an integer $p \geq 1$ depending only on $L$, such ...
- 1
-1
votes
Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's
It says the constraints are
Odd number of A's and
At most 4 B's
let's start the expression
->string may start with both A & B
======>(A+B)
->say the first letter of the string be A
=====...
1
vote
How are regular languages not structurally recursive?
Regular languages don't have recursive structures, so formally regular expressions cannot express recursive structures by definition.All regular languages can be recognized by a finite automaton. A ...
- 468
5
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
So far every language that I saw containing modulo was a regular language.
As John L. notes, that's a very good observation. Indeed, any language where the only constraint on words is that some ...
- 2,010
1
vote
Accepted
Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?
Regular languages are closed under reversal, therefore $L^R = \{v^R \mid v \in L\}$ is regular. Moreover, regular languages are closed under concatenation, therefore $L' = L \circ \{\#\} \circ L^R$ is ...
- 23.4k
5
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
Lucky enough, your case is quite easy. The language is defined by the rule "total number of letters, modulo 3, equals total number of a's, modulo 3". This is equivalent to "number of ...
- 25.2k
11
votes
Accepted
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
$\newcommand{\m}{\operatorname{\%}}$
Let $d(w)=(|w|-\#_a(w))\m3$, where $n\m 3$ is the remainder of dividing $n$ by $3$ as defined in almost every programming language.
Note $L=\{ w\mid d(w)=0\}$.
...
- 34.1k
6
votes
Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?
The following language is not regular $L = \{a^n b^m c^n \mid m = n \bmod 2\}$.
To see that $L$ is not regular, suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. ...
- 23.4k
1
vote
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
The language $\mathrm{half}(L)=\{x\mid xy\in L,|x|=|y|\}$ can be quite complicated, compared to the original language $L$. I am afraid that there is no simple construction and we have to keep track of ...
- 27.6k
2
votes
Accepted
Why is $L=\{w~|~\#_a(w) \ge \#_b(w)\}○\{w~|~\#_a(w) \le \#_b(w)\}$ regular?
The result of this concatenation is $\Sigma^*$, which is regular.
I will leave it to you to verify this is the case.
- 10.8k
1
vote
Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language
Your operation is very general, and in its generality your conjecture is not true.
For instance take for $o$ the identity, then we get the simple example $o(\{a,b\}^*) = \{wcw\mid w\in \{a,b\}^*\}$ ...
- 27.6k
1
vote
If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular
Start with an automaton for $L$, with states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. Construct a new automaton whose set of states is $Q \times 2^Q$. After ...
- 270k
2
votes
Accepted
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
If $L$ is regular , then FirstHalves or $Half(L)$ is also regular.
Algorithm:
Design $DFA, M$ of language $L$
Find the reversal of $DFA$ ,$M$ , say $N.$
Traverse $M$ for one transition (for given $\...
- 468
1
vote
How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language
I guess this question Prove half(L) is regular is the same.
There are several ways to prove a language is regular:
By building DFA, NFA, or Regular Expression (which is the case in your question).
...
- 456
1
vote
CFL with regular substitution to make a regular language
Yes, you can.
For instance: with language $L = \{a^nb^n \mid n\ge0\}$
and mapping $h(\epsilon)=\epsilon, h(a)=a, h(b)=a$ (which I think is what you meant to write), $h(L) = (aa)^*$.
What is more: ...
- 4,676
0
votes
How to prove non-regularity with Myhill-Nerode theorem?
Notice that it's preferable in that case (and in general too) to use the conclusion of myhill-nerode theorem which is: if there are infinite strings such that every two strings $w,s$ satisfies $w\not\...
- 456
1
vote
CFL with regular substitution to make a regular language
No,by your defined substitution CFLs remains CFLs.
For example, $\{a^nb^n \mid n\ge0\} = \{\epsilon,ab, aabb, aaabbb,.......\}.$
After substitution by $h(a) = a$ and $h(b) =b$,$h(\epsilon) = \epsilon$ ...
- 468
5
votes
Accepted
Decide whether regular language contains a word $w$ for which $|w| = n^2$
Convert $M$ to an NFA over $\Sigma = \{a\}$ by renaming all labels on edges to $a$. The language accepted by the NFA has the same word lengths as $T(M)$. Convert the NFA to a DFA. After removing ...
- 270k
1
vote
How would I design a State Diagram (FSM) for a AC unit?
Your question's answer could be solved by Finite Automata with output that is Moore Machine or Mealy Machine.
You have three cases:
$Case:1$ When temperature is equal or more than $80°$ then output is ...
- 468
3
votes
Accepted
Is the given language regular, CFL or in P
If a word is in your language, then it is of the form $w_1w_2$, where $|w_1| = |w_2|$ and $w_1$ contains a balanced string of length $100$, say $y$. Note that there are finitely many options for $y$. ...
- 270k
0
votes
Accepted
CFG to RG Conversion
No, you can't convert context free grammar into regular grammar in general. Because CFG is $Type{-}2$ grammar which has less restriction than $Type{-}3$ RG grammar. CFG generate more complex languages ...
- 468
1
vote
Decidability of intersection of regular and decidable languages
I don't quite understand what you mean by if (A) is decidable then it is a language in R, if you mean that A is regular and B is regular then the intersection of two regular languages is still regular....
- 456
Top 50 recent answers are included