0

I want to draw the DFA of the language that is given of the following expression, but I got stuck... Let the expression be {$(xy)^{*},(zx)^{+}$}$xz$ . Could you help me understanding which language it is?

Mary Star
  • 13,956

1 Answers1

0

Let $L$ be the language. Every word of $L$ is

$$\underbrace{xyxyxy\ldots xy}_{n\text{ pairs }xy}\underbrace{zxzxzx\ldots zx}_{m\text{ pairs }zx}xz$$

for some $n\ge 0$ and $m\ge 1$. That is, it must be $0$ or more copies of $xy$, followed by one or more copies of $zx$, followed by a single $xz$. The shortest possible word in $L$ is $zxxz$, with $n=0$ and $m=1$. The next-shortest are $zxzxxz$, with $n=0$ and $m=2$, and $xyzxxz$, with $n=m=1$.

If you’ve already learned about regular grammars, the following may be helpful in getting a handle on $L$. A regular grammar with the following productions generates $L$; $S$ is the initial symbol.

$$\begin{align*} &S\to xyS\mid Z\\ &Z\to zxZ\mid zxxz \end{align*}$$

Every derivation from this grammar begins by applying the production $X\to xyS$ $n$ times for some $n\ge 0$, followed by the production $S\to Z$; at that point we’ve generated the string $(xy)^nZ$. Then the production $Z\to zxZ$ is applied $k$ times for some $k\ge 0$, and the derivation must conclude with an application of $Z\to zxxz$ to get rid of the non-terminal symbol. At that point we have $(xy)^n(zx)^kzxxz$ for some $n,k\ge 0$; if we set $m=k+1$, we can write the same string as $(xy)^n(zx)^mxz$, where $n\ge 0$ and $m\ge 1$.

Brian M. Scott
  • 616,228
  • Would the anonymous downvoter care to explain what’s wrong? Or justify the misleading vote? – Brian M. Scott Dec 08 '13 at 22:02
  • Great, I think I understood it!!! Because I don't know how to post the DFA I post the state diagram, so that you can tell me if it's right.

    Q1--y-->Q1, Q1--x-->Q2, Q1--z-->Q4, Q2--y-->Q3, Q3--x-->Q2, Q3--z-->Q4, Q4--x-->Q5, Q5--z-->Q4, Q5--x-->Q6, Q6--z-->Q7, with final state Q7

     – Mary Star Dec 08 '13 at 22:27
  • 1
    @Mary: The transition $q_1\overset{y}\longrightarrow q_1$ definitely can’t be right: it lets you start with a whole string of $y$’s. Also, you’re missing some transitions: for instance, you’ve no $y$ or $z$ transition from $q_4$, and no transitions at all from $q_6$. For a DFA, rather than an NFA, you really do need those transitions. To get started, if $q_1$ is your initial state, you want $q_1\overset{x}\longrightarrow q_2$ and $q_2\overset{y}\longrightarrow q_1$ to give you the initial $xy$ pairs, and $q_1\overset{z}\longrightarrow q_3$ to get a start on the $zx$ pairs, and something ... – Brian M. Scott Dec 08 '13 at 22:35
  • 1
    ... like $q_1\overset{y}\longrightarrow q_{\text{trap}}$ with $q_{\text{trap}}\overset{x,y,z}\longrightarrow q_{\text{trap}}$ to kill off any words that start with $y$. – Brian M. Scott Dec 08 '13 at 22:36
  • So, is it like that: $q_{1}$--y-->$q_{trap}$, $q_{1}$--x-->$q_{2}$, $q_{1}$--z-->$q_{3}$, $q_{2}$--y-->$q_{1}$, $q_{3}$--x-->$q_{4}$, $q_{4}$--z-->$q_{3}$, $q_{4}$--x-->$q_{5}$, $q_{5}$--z-->$q_{6}$, what about $q_{2}$--x,z-- ??, $q_{3}$--y,x-- ??, $q_{4}$--y-- ??, $q_{5}$--y,x-- ?? – Mary Star Dec 08 '13 at 23:24
  • 1
    @Mary: Everything that you have is okay, so it’s just a matter of filling in the missing ones. The trap state should have $x,y$, and $z$ transitions to itself. If you’re in $q_2$ and get an $x$ or a $z$, the input string can’t be in $L$, so you should go to the trap state. (I think of it as the dump, where you throw all of the bad strings.) The same goes for all of the other missing transitions that you asked about, and for all three transitions from $q_6$. Finally, you need to specify that $q_6$ is the only acceptor state (and of course that $q_1$ is the initial state). – Brian M. Scott Dec 08 '13 at 23:32
  • Great!!!Thank you very much!!! – Mary Star Dec 09 '13 at 17:52
  • Could you tell me also the difference between {$a,b$}$^{}$ and $(a,b)^{}$ ? – Mary Star Dec 09 '13 at 17:58
  • @Mary: You’re very welcome. ${a,b}^$ is just the set of all finite strings of $a$’s and $b$’s; I’ve not seen the notation $(a,b)^$ before and really don’t know how to interpret it. Do you have a context for it? – Brian M. Scott Dec 09 '13 at 18:30
  • The expression is: ({{a,b}$^$,(0,c)$^$})$^*$ – Mary Star Dec 09 '13 at 19:05
  • @Mary: My immediate reaction is that it simply doesn’t make sense. The outermost pair of parentheses appears to serve no purpose, and the rest is just ... weird. I’d have to see the whole setting in which it appears, and even then I might not be sure of what’s intended. – Brian M. Scott Dec 09 '13 at 19:10
  • I'm given that expression above and I have to draw the DFA/NFA. – Mary Star Dec 09 '13 at 19:16
  • @Mary: I’d have to see more of the notation that your source is using; that expression really doesn’t make sense to me. Does the problem specify what the input alphabet is? – Brian M. Scott Dec 09 '13 at 19:24
  • No I'm only given this expression, but I think that the input alphabet is {a,b,c}.. With 0 I mean $\varnothing $ – Mary Star Dec 09 '13 at 19:29
  • @Mary: So the language is described as $$\left(\left{{a,b}^,(\varnothing,c)^\right}\right)^*;?$$ – Brian M. Scott Dec 09 '13 at 19:33
  • I have to draw the DFA/NFA that accepts the language of the regular expression above. – Mary Star Dec 09 '13 at 19:37
  • @Mary: I don’t think that I can help: that’s not a well-formed regular expression in any of the notations for regular expressions with which I’m familiar. If it’s from a book, and I had the book in front of me, I might be able to work out what’s intended, but the expression alone just doesn’t give me enough context to make a reasonable guess. – Brian M. Scott Dec 09 '13 at 19:41