Explore BrainMass
Share

# Automata Theory, Grammars and Languages

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

(1) A gate with three rotating arms at waist height is used to control access to a subway in New York city. Initially, the arms of the gate are locked preventing customers from passing through. Unlocking the arms requires depositing a token in a slot, which allows the arms to rotate to a complete turn which allows one customer to push through and enter. Once the customer passes through the arms are then locked again until another customer deposits another token in the slot.

The gate has two states: LOCKED and UNLOCKED. It also has two inputs: TOKEN and PUSH. When the gate is locked, pushing the arm of the gate has no effect regardless of how many times it is pushed. The input TOKEN changes the state from LOCKED to UNLOCKED. When the gate is in the UNLOCKED state, inserting additional tokens has no effect on the state. But when in the UNLOCKED state, a PUSH input changes the state to LOCKED.

(i). Provide a transition table showing each state, the inputs, and the resulting new states for each input

(ii). Represent your transition table into a digraph (transition diagram)

(2) Here is a context-free grammar that can be used to generate algebraic expressions via the arithmetic operators (addition, subtraction, multiplication, and division), in the variables p, q, and r. The letter E stands for expression:

Rule 1: E —› p

Rule 2: E —› q

Rule 3: E —› r

Rule 4: E —› E + E

Rule 5: E —› E - E

Rule 6: E —› E X E

Rule 7: E —› E/E

Rule 8: E —›(E)

(i). Use the above grammar to derive the string given by the mathematical expression E = (p + q) X p - r X p/(q + q)

(ii). Provide a parse tree for this derivation.

https://brainmass.com/math/discrete-math/automata-theory-grammars-and-languages-590617

#### Solution Preview

Automata Theory, Grammars and Languages
(1) A gate with three rotating arms at waist height is used to control access to a subway in New York city. Initially, the arms of the gate are locked preventing customers from passing through. Unlocking the arms requires depositing a token in a slot, which allows the arms to rotate to a complete turn which allows one customer to push through and enter. Once the customer passes through the arms are then locked again until another customer deposits another token in the slot.
The gate has two states: LOCKED and UNLOCKED. It also has two inputs: TOKEN and ...

#### Solution Summary

Solution describes subway turnstile in terms of a transition table, and uses context free grammar to construct a specified sentence.

\$2.19

## Write a general statement that describes when a string is part of the language generated by given automata and when that string is not in the language.

Automata theory involves the study of mathematical objects called automata and the computational problems that can be solved using them. Context-free grammar provides us with mathematical techniques of building phases in a language from other blocks that are smaller. Visual structures called parse trees enable us to clearly differentiate which phrases are unique and which ones are ambiguous.

A finite-state automaton is given by the 5-tuple (Q, ∑, δ, q, F), where

Q = the finite set of states = {A, B, C}

∑ = the Alphabet (inputs) = {x, y}

δ = the transition function using the alphabet as inputs to the states

q = the initial state = {A}

F = Accepting (or final) state = {C}

The transition table for the automaton is given by the table in the attachment.

(i) Draw the corresponding transition diagram (digraph).

(ii) Provide 5 strings that are in the language generated by the automaton.

(iii) Provide 5 strings, that use the same inputs, which are not in the language generated by the automata.

(iv) Write a general statement that describes when a string is part of the language generated by the given automata and when that string is not in the language.

View Full Posting Details