SET PYQs from Unit-8

Which of the following is/are type of data supported/added by/in typical object file formats in code generation phase of a compiler?
(i) Data segment
(ii) Block started by symbol
(iii) Text segment

Data segment: This section holds initialized global variables. It's read/write.
Block started by symbol (BSS): This section holds uninitialized global variables.
Text segment: This section contains the executable machine code. Also known as the code segment. 

All the three options are correct!

Which one of the following is not decidable?
 (A) Given a Turing machine M, a string S and an integer K, M accepts S with K step S
 (B) Equivalence of two given Turing machines
 (C) Language accepted by a given DFSA is non-empty
 (D) Language generated by a CFG is non-empty

A problem is decidable if there exists a Turing machine that can always determine the correct answer in a finite number of steps.
Otherwise, the problem is undecidable, it means no algorithm can guarantee a correct answer for all cases.

A is decidable because the number of steps is bounded.
A simulation of running on S for at most K steps can always provide an answer  

B is undecidable.
The Turing machine equivalence problem asks whether two machines accept the same language, but due to the halting problem, there is no general procedure that can always determine equivalence.  

C is decidable, because a DFSA has a finite number of states and transitions.
We can check if any accepting state is reachable from the start state.  

D is decidable. T
his can be solved by checking whether there exists a derivation that produces a string using the given CFG.  

Determine the regular expression for the language accepted by L1/L2 for L1 = L(a*baa*), L2 = (ab*) :

Reference book: 

Peter Linz. An Introduction to Formal Languages and Automata, Latest Edition, Jones and Bartlett.
This book's 6th edition is available in the web.

This problem is explained in Example 4.5

Determine the context free grammar for the following language where n, m >= 0 :
 L { w belongs to  { a,b }* | count of a(v) = count of b(v) , where v is any prefix of w}

Prefix is a pattern which occurs in the starting of the string.
The given language consists of strings in {a, b}* such that, in every prefix, the number of occurrences of 'a' equals the number of occurrences of 'b'.
This property strongly suggests a need for balancing 'a' and 'b' throughout the derivation process.  

 (A) S -> A | B
       A -> aA | aS | epsilon
       B -> bB | epsilon

Option A doesn't enforce strict balancing at every prefix.

(B) S -> A | B
      A -> aA | aS | epsilon
      B -> bB | bS | epsilon

Option B allows transitions between 'a' and 'b' but doesn’t maintain balance in every prefix.

(C) S -> A | B
      A -> aA | aB | epsilon 
      B -> bB | epsilon  

Option C correctly ensures that every prefix maintains balance by switching between 'a' and 'b'

(D) S -> A | B
      A -> aA | SS | epsilon
      B -> bB | bA | epsilon

Option D introduces non-standard transitions that don’t guarantee proper prefix balancing.

The CFG can be: 
S -> aSbS I bSaS | epsilon
to make sure a's count = b's count.

Determine the state table of a minimal machine which produces and maintains an output of 1 wherever it detects the sequence 001. The output returns to zero only when another sequence 010 is detected.

This problem is based on Moore and Mealy machines from Finite State Automata.

These machines have the capability of giving an output.

Mealy machine gives output after every transition. It means, if i say 0/1 it means for input 0, the output is 1 (output values are determined by both current state and current input)

Moore machine gives output based on current state after each transition (the output value is attached to the state)

Sequence 001 should give 1 as output. Only Sequence 010 should return to 0

Anything other than 0 and 1 in the output i have mentioned as 'a' (small letter of A). 

Reason for using 'a': only one sequence can give 0, only one sequence can give 1, remaining sequences should NOT give 0 or 1, so 'a' is used.

There are two ways of interpreting the input:

If you take: 00101001 = this is overlapping sequence we can take 001, 010 from first 4 digits. 

so we can have 2 diagrams - one for overlapping, one for non overlapping. 

In this question, 010 should only give 0, so we can consider it as non overlapping sequence.
It means in 00101001 we can take 001-010-01 separately.

There is a hint in the question: return to zero only when 010 is detected  - this means resetting to the initial state.

If we reset to initial state, then we cannot draw diagram for 2 sequences.

I will provide both Mealy and Moore machines for the above question to differentiate their implementation.

This is a descriptive question from UGC NET Paper-3.
Aspirants can use this implementation for your learning purpose to understand how this machine works.
Implementations may differ.