in Theory of Computation edited by
100 views
0 votes
0 votes

 isn’t this language regular?

it’s nfa according to me

in Theory of Computation edited by
100 views

1 Answer

1 vote
1 vote
Best answer
It is not Regular, this comes due to (y$z^{n}$)${^k}$

Regular Language/ Finite automata doesnt have memory.

The language is to accept y$z^{n}$ ‘k’ times.

i.e. if n = 2 and k = 3, yzz yzz yzz all three times. The automata has to REMEMBER y$z^{n}$ and everytime repeat only that, i.e whatever the first time value of n was, the automata has to accept ‘k’ times only that value of n.
Going by the NFA you made, if I want n=2,k=3 (m=X): $x^{X}$yzzyzzyzz, Then your NFA can also accept $x^{X}$yzzzzzzyzyzzzzz (fails to regulate the value of z) Hence a memory/stack is needed.

Language is atleast CFL
selected by

1 comment

well caught
1
1