For each of the languages L1, L2, L3, L4 described below: Write a regular expres
ID: 3109741 • Letter: F
Question
For each of the languages L1, L2, L3, L4 described below: Write a regular expression for the language. Define a finite state machine (FSM) that recognizes words in the language (input alphabet, states, start state, state transition table, and accept states). Include a state digraph for the FSM. L1: For alphabet {a, b}, all strings that contain an odd number of a's and exactly one b. L2: For alphabet {0, 1}, all strings of length 3 or less that have more 0's than 1's. L3: For alphabet {x, y, z}, all strings that contain xyx or zyz. L4: For alphabet {p, q, r}, all strings that contain the substring square or end with pp.Explanation / Answer
1). 1. and {L} are regular languages.
" s ΠS : {a} is a regular language.
2. If L is regular, L* is regular.
If L1 and L2 are regular, then L1L2 and L1»L2 are regular.
3. No other languages over S are regular.
2)
simply a state machine, is a mathematical model of computation. It is anabstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. A FSM is defined by a list of its states, its initial state, and the conditions for each transition.
The behavior of state machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Examples arevending machines, which dispense products when the proper combination of coins is deposited, elevators, whose sequence of stops is determined by the floors requested by riders, traffic lights, which change sequence when cars are waiting, andcombination locks, which require the input of combination numbers in the proper order.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.