Finate State Machine

★★★★★

0 votes

Details

Problem

A finite state machine (sometimes called a finite state automaton) is a computation model that can be implemented with hardware or software and can be used to simulate sequential logic and some computer programs.

For more information read https://en.wikipedia.org/wiki/Finite-state_machine

‘A’ is starting state, ‘E’ and ‘C’ and accepting states.

You are given a String and check whether the above FSM accepts the string.

Example:

S=”abaa”

(A,”abaa”)->(B,”baa”)->(E,”aa”)->(B,”a”)->C

As ‘C’ is accepting state, string S is accepted by the above FSM.

Input format

First line: An integer N denoting the number of test cases
Each test case contains a string

Output format

For each test case, prints YES or NO whether the string is accepted by FSM

Constraints

1<=N<=1000

1<=LEN(S)<=10000

Sample Input

5
aabaabbbab
bbbbbbabba
abaabbbabb
baabaabbbb
bbbbbaabba

Sample Output

Yes
No
No
No
No

Time Limit: 5

Memory Limit: 256

Source Limit:

Contributers:

B DINESH