Nitya is a digital circuit designer. She decides to design a sequence detector which may…
- User
Nitya is a digital circuit designer. She decides to design a sequence detector which may be either an overlapping model or a non-overlapping model.
Sequence detector is a digital circuit which is used to detect the sequences from a series of numbers. These detectors may be overlapping or non-overlapping.
Example of how non-overlapping sequence detector detects sequence 101 is depicted below.
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@31c7c281:image1.jpeg
So, from the series given above, say Series 1, non-overlapping sequence detector detects four 101 sequences
Example of how overlapping sequence detector detects sequence 101 is depicted below
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@31c7c281:image2.png
From the series given above, say Series 2, overlapping sequence detector detects three 101 sequences. The last 5 digits in the given series i.e., 10101 has two 101 sequences where the middle 1 is used by both left and right trailing digits.
The process of any circuit design starts with requirements and state transition diagram to represent that requirement. So, Nitya asked her assistant to create different state transition diagrams for the hardware needed to detect different sequences. Hardware will need to be customized per sequence. The assistant designed different hardware for different sequences, but forgot to mention the sequence to be detected on respective state transition diagrams. So now, Nitya must go through every sequence and determine, what is the sequence to be detected and whether the sequence detector is overlapping or non-overlapping.
So, she decides to code the state transition diagram and find which sequence is to be detected and what is the type of detector.
Constraints 2 <= Length of sequence <= 10
Each input line contains 4 space separated inputs viz. < present_state (char), next_state (char), input (0/1), output (0/1)>
4 < = Number of lines of input < = 20
For a sequence to be detected, every state must be visited at least once and the number of transitions should be equal to Number of states
A given state transition diagram always corresponds to one sequence. As explained in Input section, the number of chars will depict the number of states in a state transition diagram
Input Input consists of variable number of lines of input where each line contains 4 space separated inputs which represents present_state (char), next_state (char), input (0/1), output (0/1) of the state transition diagram.
Output Print the sequence to be detected in first line.
Print the type of sequence detector in the second line. If the detector is non-overlapping print "Non Overlapping Sequence Detector" else print "Overlapping Sequence Detector".
Input
a b 1 0
b c 0 0
b b 1 0
a a 0 0
c a 0 0
c a 1 1
Output
101
Non Overlapping Sequence Detector
- Assistant
101 Non Overlapping Sequence DetectorExplanation:
Given the state transitions:
a b 1 0 b c 0 0 b b 1 0 a a 0 0 c a 0 0 c a 1 1-
Sequence Detection:
- Starting at state a:
- Input 1 → Transition to b (input so far:
1)
- Input 1 → Transition to b (input so far:
- From b:
- Input 0 → Transition to c (input so far:
10)
- Input 0 → Transition to c (input so far:
- From c:
- Input 1 → Transition to a with output 1 (input so far:
101)
- Input 1 → Transition to a with output 1 (input so far:
Thus, the detected sequence is 101.
- Starting at state a:
-
Detector Type:
- The state transitions indicate that once a sequence
101is detected, the detector resets to the initial state without reusing any part of the detected sequence for subsequent detections. - This means sequences do not overlap, classifying it as a Non Overlapping Sequence Detector.
- The state transitions indicate that once a sequence
-