Automation

0

0 votes
Medium
Problem

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as a deterministic finite acceptor (DFA) and a deterministic finite state machine (DFSM) or a deterministic finite state automaton(DFSA)—is a finite-state machine that accepts and rejects strings of symbols and only produces a unique computation (or run) of the automaton for each input string. Deterministic refers to the uniqueness of the computation. In search of the simplest models to capture finite-state machines, McCulloch and Pitts were among the first researchers to introduce a concept similar to finite automata in 1943. (Referred from Wikipedia).

You have to design a program that accepts and designs a DFA in x,y in accordance to the user and also accepts strings and results in whether that machine accepts that string or not.

Input:

1st line accepts the number of states in the machine(n)

2nd line contains 2 numbers as initial and final states

Next 2*n line has all the links in the order 1 x 3, symbolizing that from state 1 if x is read then it goes to state 3

Next line(after 2n lines) will take a number as in how many tests to be done(n1)

Next n1 lines will have strings in x and y of any length.

 

Output:

n1 lines having a YES if it is accepted or else NO.

Example:

Input:

5

1 3

1 x 2
1 y 5
2 y 4
2 x 5
3 x 5
3 y 2
4 x 3
4 y 2
5 x 4
5 y 3

3

xxy
xyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyxy
xxx

Output:

YES
YES
NO


 


 


 

Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?