CS402 Final Term Solved Subjective with References by Moaaz

Solved Subjective · From Final term Papers · Feb 14,2013 · PSMD01 · Spring 2012

What is the concept of the Union of FA's ?

Answer: (Page 32) FA3 be an FA corresponding to r1+ r2, and then the initial state of FA3 must correspond to the initial state of FA1 and the initial state of FA2.

What does mean the LANGUAGE IS CLOSED?

Answer: (Page 90) Closed w.r.t. concatenation i.e.the language expressed by RE of type r*.

Stack consistence means that in the PDA?

Answer: (Page 123) when a row pops a character it should be there at the top of the STACK

-Where Null string is use the most?

Answer: The choice of null string depends on the requirements of the language. In some case we need to have null string to be accepted by the FA.

PUSHDOWN AUTOMATON (PDA)?

Answer: (Page 119) PUSHDOWN STACK or PUSHDOWN STORE PUSHDOWN STACK is a place where the input letters can be placed until these letters are referred again. It can store as many letters as one can in a long column. Initially the STACK is supposed to be empty i.e. each of its storage location contains a blank.

Prefixes of a language in another language?

Answer: (Page 78) Prefixes of a language in another language If two languages R and Q are given, then the language the prefixes of Q in R denoted by Pref(Q in R) is the set of strings of letters that, when concatenated to the front of some word in Q to produce some word in R i.e. Pref(Q in R) = the set of all strings p such that there exists words q in Q and w in R such that pq = w. Following are the examples in this regard Example Let Q = {aa,abaaabb,bbaaaaa,bbbbbbbbbb} and R = {b,bbbb,bbbaaa,bbbaaaaa} It can be observed that aa and bbaaaaa occur at the ending parts of some words of R, hence these words help in defining the language pref(Q in R). Thus pref(Q in R) = {b,bbba,bbbaaa}

Conversion form of PDA?

Answer: (Page 119)

Conversion form of PDA

A PDA is in conversion form if it fulfills the following conditions: There is only one ACCEPT state. There are no REJECT states. Every READ or HERE is followed immediately by a POP i.e. every edge leading out of any READ or HERE state goes directly into a POP state. No two POPs exist in a row on the same path without a READ or HERE between them whether or not there are any intervening PUSH states (i.e. the POP states must be separated by READs or HEREs). All branching, deterministic or nondeterministic occurs at READ or HERE states, none at POP states and every edge has only one label. Even before we get to START, a “bottom of STACK” symbol $ is placed on the STACK. If this symbol is ever popped in the processing it must be replaced immediately. The STACK is never popped beneath this symbol. Right before entering ACCEPT this symbol is popped out and left. The PDA must begin with the sequence

The entire input string must be read before the machine can accept the word.

Is automata is a programming subject or theoretical ??? marks 3

Answer: In theoretical computer science, automata theory is the study of mathematical objects called abstract machines or automata and the computational problems that can be solved using them. Automata mean "self-acting".

Automata theory is also closely related to formal language theory. An automaton is a finite representation of a formal language that may be an infinite set. Automata are often classified by the class of formal languages they are able to recognize.

Parsing Techniques (5 number)

Answer: (Page 136) Recall the CFG for arithmetic expression S→S+S|S*S|number It was observed that the word 3+4*5 created ambiguity by considering its value either 23 or 35. To remove this ambiguity, the CFG was modified to S→(S+S)|(S*S)|number There arises a question that whether a new CFG can be defined without having parentheses with operator hierarchy (i.e. * before +)? The answer is yes. Following is the required PLUS'TIMES grammar S→E, E→T+E|T, T→F*T|F, F→(E)|i Where i stands for any identifier i.e. number or of storage location name (variable). Following is the derivation of i+i*i S ⇒E ⇒T+E

⇒F+E ⇒i+E

⇒i+T ⇒i+F*T

⇒i+i*T ⇒i+i*F ⇒i+i*i

-What are live and dead productions. (5 number)

Answer: (Page 127) Live production: A production of the form nonterminal → string of two nonterminals is called a live production. Dead production: A production of the form nonterminal → terminal is called a dead production.

Spring 2012

1: How can we define languages elaborate any five ways.

Answer: (Page 4) Defining Languages The languages can be defined in different ways , such as Descriptive definition, Recursive definition, using Regular Expressions (RE) and using Finite Automaton (FA) etc.