Recent questions tagged regular-expression

Prove that $(L^{*}M^{*})^{*}=(L+M)^{*}.$Complete the proof by showing that strings in $(L^{*}M^{*})^{*}$ are also in $(L+M)^{*}.$

We developed the regular expression $(0+1)^{*}1(0+1)+(0+1)^{*}1(0+1)(0+1)$ Use the distributive laws to develop two different,simpler,equivalent expressions.

Prove or disprove each of the following statements about regular expressions.$(R+S)^{*}=R^{*}+S^{*}$$(RS+R)^{*}R=R(SR+R)^{*}$$(RS+R)^{*}RS=(RR^{*}S)^{*}$$(R+S)^{*}S=(R^{*...

Verify the following identities involving regular expressions.$R+S=S+R$$(R+S)+T=R+(S+T)$$(RS)T=R(ST)$$R(S+T)=RS+RT$$(R+S)T=RT+ST$$(R^{*})^{*}=R^{*}$$(\in+R)^{*}=R^{*}$$(R...

Give a regular expression to represent salaries as they might appear in employment advertising. Consider that salaries might be given on a per hour, week, month or year b...

Give a regular expression to describe phone numbers in all the various forms you can think of. Consider international numbers as well as the fact that different countries...

Convert the following regular expressions to NFA's with $\in-$transactions. $01^{*}$$(0+1)01$$00(0+1)^{*}$Eliminate $\in-$transactions from your $\in-NFA’s$

Convert the following regular expressions to NFA's with $\in-$transactions.$01^{*}$$(0+1)01$$00(0+1)^{*}$

Convert the following DFA to a regular expression using the state elimination techniques.

Here is a transition table for a DFA$:$Give all the regular expressions $R_{ij}^{0}.$ Note$:$Think of state $q_{i}$ as if it were the state with integer number $i.$ Give ...

Here is a transition table for a DFA$:$ Give all the regular expressions $R_{ij}^{0}.$ Note$:$Think of state $q_{i}$ as if it were the state with integer number $i.$ Give...

Give English descriptions of the languages of the following regular expressions$:$$(1+\in)(00^{*}1)^{*}0^{*}$$(0^{*}1^{*})^{*}000(0+1)^{*}$$(0+10)^{*}1^{*}$

Write regular expressions for the following languages$:$The set of all strings of $0's$ and $1's$ not containing $101$ as a substring.The set of all strings with an equal...

Write regular expressions for the following languages$:$The set of strings over alphabet $\{a,b,c\}$ containing at least one $a$ and at-least one $b.$The set of strings o...

Consider the following generalized transition graph.(a) Find an equivalent generalized transition graph with only two states.(b) What is the language accepted by this gra...

Find the minimal dfa that accepts $L(a^*bb) ∪ L(ab^*ba)$.

Find an nfa for all strings not containing the substring 101. Use this to derive a regular expression for that language.

Find dfa's that accept the following languages.(a) $L (aa^* + aba^*b^*)$.(b) $L (ab (a + ab)^* (a + aa))$.(c) $L ((abab)^* + (aaa^* + b)^*)$.(d) $L (((aa^*)^* b)^*)$.

Give an nfa that accepts the language $L((a + b)^* b(a + bb)^*)$.

Find an nfa that accepts the complement of the language in $L (ab^*aa + bba^*ab)$.

Formal languages can be used to describe a variety of two-dimensional figures. Chain-codelanguages are defined on the alphabet $Σ =$ {$u, d, r, l$ }, where these symbols ...

For the case of a regular expression $r$ that does not involve $λ$ or $Ø$, give a set of necessary and sufficient conditions that $r$ must satisfy if $L(r)$ is to be infi...

Prove rigorously that the expressions in $r= (1^*011^*)^* (0 + λ) + 1^* (0 + λ)$ do indeed denote the specified language.