CODEWITHSUNDEEP
regular-languagefinite-automatanfa
MehraD
MehraD

Reputation: 176

design NFA which accepts specific length of strings

Im looking forward to design a FA which accepts some kind of string that accept some A and B.

First a string which the number of A is five more times higher than B.

i mean L={w∈{A,B}* and (nA(W)-nB(W) mod 5=0)

And also a FA which accept different number of character in a string:

L={A^n B^m C^k | n,k>0 and m>3}

I design some FAs But they did not work perfectly on this complicated strings.

Any help on how should i design this ?

Upvotes: 0

Views: 1754

Answers (1)

Alex
Alex

Reputation: 11

Unfortunately, your questions are confusing as the english text doesn't agree with the mathematical formula. I will try to answer to these four questions then:

  • A language which consists of string over {a,b} that the number of a (= #a(w)) is five times as the number of b ( #b(w)), L = { w in {a,b}* : #a(w)>#b(w) and #a(w)=#b(w)mod5 }

    This cannot be done by an NFA. The proof is simple by using the pumping lemma (P.L) with the string a^pb^5p, where p is the constant of P.L.

  • For the language: L={w∈{A,B}* : (nA(W)-nB(W)) mod 5=0} that you wrote, you can do it with an DFA that consists of a cycle of 5 states.

    The transitions are, if you read a go clockwise if you read b go counter-clocwise. Choose at random one state to be initial state and the same state will be the final state.

  • For the language L={A^n B^m C^k | n,k>0 and m>3}, it should be easy to find out if you read L as L=A(A)* B(B)* c^4(C)*

  • For the language that accepts different number of character in the string (let's say over a,b). The language should be R={ w in {a,b}* : #a(w) not equal #b(w)}

    This language again it cannot be recognized by an NFA. If this language was regular (recognzied by an NFA) so would be this language:

    L=a*b* intersection (R complement). The language L is {a^n b^n/ n non-negative integer}.

    The language L is the first example of most books when they speak about languages that are non-regular.

Hopefully, you will find this answer helpful.

Upvotes: 1

Related Questions