New answers tagged

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 ...
user avatar
  • 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\{\...
user avatar
  • 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 ...
user avatar
-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 =====...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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\}$. ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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.
user avatar
  • 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\}^*\}$ ...
user avatar
  • 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 ...
user avatar
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 $\...
user avatar
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). ...
user avatar
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: ...
user avatar
  • 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\...
user avatar
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$. ...
user avatar
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 ...
user avatar
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....
user avatar

Top 50 recent answers are included