0
$\begingroup$

Let $(Q,\Sigma,\delta, q_0, F)$ be a finite automaton, does $$ (q_1a+q_2b)c=q_1ac+q_2bc $$

hold for any $q_1,q_2\in Q$ and $a,b,c\in \Sigma$?

Here $Sa=\{\delta(q, a)\mid q\in S\}$ and $qa=\{q\}a$ for any $S\subseteq Q$, $q\in Q$ and $a\in\Sigma$. The operation "$+$" means set union.

$\endgroup$
1
$\begingroup$

since someone has edited the question, the question seems much more meaningful , and yes the above equality holds , here the equations

taking LHS of the equation

= ( $q_1$a $+$ $q_2$b ) c

=$\delta$ ( ( $q_1$a $+$ $q_2$b ) , c ) { as you defined Sa={ δ (q,a) ∣q ∈ S} }

=$\delta$ ( ( $q_1$a ) $\bigcup$ $q_2$b ) , c )

=$\delta$ ( ( $q_1$a),c )) $\bigcup$ $\delta$ ( ( $q_2$b ) , c )

=$q_1$ ac $+$ $q_2$bc

which is equal to RHS.

$\endgroup$
0
$\begingroup$

As pointed out by others your regular expression is wrong until you did not correct your definition of $q_1$ and $q_2$ to some input alphabets also i assume the same for a,b and c . If you correct this then your regular expression would make sense.

You first have to understand that a Regular expression is not an equation you can form from whatever (as you did by combining states and input alphabets) because regular expression denotes a "Set" in formal terms a "regular set". So any regular expression like "a + b" denotes regular set containing {a,b} as its elements .

Secondly there are specific rules to form the regular expression which accompany primitive regular expression and the operation you can define on them. Primitive are :

  1. an input alphabet like "a" is a regex , in regular set it is {a}

  2. an empty string "$\epsilon$" is a regex , in regular set it is {$\epsilon$}

  3. a set that have no string that is "$\varphi$ ", in regular set it is empty set { }

Operation the above regular expression are : 1. union ( denoted by "+") , like " a + b " means {a ,b}

2.concatenation denoted by ( . ) , like "a . b" or simply "ab" means { ab }

  1. kleene star closure of any of a regex like "$a^*$", denotes { $\epsilon$, a, aa,aaa.....} ,also you can add an modified version of it which we say positive star closure like "$a^+$" denoting set { a, aa, aaa,aaaa,....}

so any regular expression violating above definition is not defined like "a+b+" does not convey anything . similary you are using $q_1" as state in regex so it is not correct regular expression .

further i request you to look again your question and then ask again.

$\endgroup$
0
$\begingroup$

Your equation holds. Actually, more generally, for every subsets $S_1$, $S_2$ of $Q$ and for every words $u$, $v$ and $w$, the following equality holds $$ (S_1u + S_2v)w = S_1uw + S_2vw $$ Indeed, \begin{align} S_1u &= \{ p \in Q \mid \text{there is a path of the form $s_1 \xrightarrow{u} p$ for some state $s_1 \in S_1$} \} \\ S_2v &= \{ p \in Q \mid \text{there is a path of the form $s_2 \xrightarrow{v} p$ for some state $s_2 \in S_2$} \} \\ \end{align} Therefore \begin{align} (S_1u + S_2v)w &= \{ q \in Q \mid \text{there is a path of the form $p \xrightarrow{w} q$ for some state $p \in S_1u + S_2v$}\}\\ &= \{ q \in Q \mid \text{there is a path of the form $s_1 \xrightarrow{u} p \xrightarrow{w} q$ }\\ &\qquad\qquad\quad \text{for some state $s_1 \in S_1$ and some state $p \in Q$}\} + {}\\ &\phantom{{}={}} \{ q \in Q \mid \text{there is a path of the form $s_2 \xrightarrow{v} p \xrightarrow{w} q$ }\\ &\qquad\qquad\quad \text{for some state $s_2 \in S_2$ and some state $p \in Q$}\}\\ &= \{ q \in Q \mid \text{there is a path of the form $s_1 \xrightarrow{uw} q$ for some state $s_1 \in S_1$}\} + {}\\ &\phantom{{}={}} \{ q \in Q \mid \text{there is a path of the form $s_2 \xrightarrow{vw} q$ for some state $s_2 \in S_2$}\}\\ &= S_1uw + S_2vw \end{align} This is actually a good reason to prefer this algebraic notation to the $\delta$ notation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.