Sharma Guides

Show that L = {0 n 1 n  | n≥1} is not regular. Ans.     Step-1: Suppose L is regular and we get a contradiction. Let n be the number of states in FA accepting L.     Step-2: Let w= 0 m 1 m . Then |w| = 2m>m. By pumping Lemma we write w = xyz with |xy|≤m and |y|≠0.     Step-3: We want to find n so that xy n z ∉ L for getting a contradiction. The string y can be in any of the following forms :           Case-1  y has 0's, i.e. y=0 k  for some k ≥ 1.          Case-2  y has only 1's, i.e. y=1 t  for some t ≥ 1.          Case-3  y has both 0's and 1's, i.e. y=0 k 1 t  for same k,t ≥ 1.     In case 1, we can take n = 0. As xyz = 0 m 1 m , xz = 0 m-k .1 m .     As k  ≥ 1, m-k ≠ m. So xz ∉ L.     In case 2, take n=0. As before xz is 0 m 1 m-t  and m ≠ m - t.     So xz...

Construct a regular grammar G generating the regular set represented by – P = a*b (a+b)* Ans.          Pumping Lemma for regular language :          Let,  M = (Q,  Σ, ∂, q 0 , F)  be a finite automation with n states.           Let L be regular set accepted by M. Let   w  ∈ L and |w| ≥ m.           If m ≥ n, then there exists x, y, z such that w = xyz,  z ∈Σ and xy i z∈L for each i ≥ 0.

Write a CFG which generates string of palindrome of binary number. Ans.             For constructing a grammar G of all pallindroms, we use the recursive definition as-               (i)    ^ is a pallindrome.               (ii)   0,1 are pallindroms.               (iii)   If x is a pallindrome, then 0x0 and 1x1 are also pallindroms.      ∵ The CFG, G ({S}, {0,1},P,S)      Where, P the production set, consists of =>          P : {S  →  AB|  ^  ,               A  →  0A|1A|0|1 ,               B  →  0 B|1B|0|1  }      To prove that we are correct, taking an example of a pallindrome, say, 0011100. So, it can be derived as =...

Draw the transition diagram of a finite state automation that accepts all strings over {0, 1} (a) having odd number of 0’s (b) having even number of 0’s and even number of 1’s. Ans.  (a) ( having odd number of 0’s ) Ans.  (b) ( having even number of 0’s and even number of 1’s )

Let G be a grammar s-0B | 1A, A - 0 | 0S | 1AA, B- 1 | 1S | 0BB * Let G be a grammar s →0B | 1A, A → 0 | 0S | 1AA, B→ 1 | 1S | 0BB. For the string 00110101, find (i) leftmost derivation (ii) rightmost derivation (iii) derivation tree Ans.  (i) S → 0B → 00BB → 001SB → 0 01SB → 0 01/AB → 00110B → 0 01101S → 0011010B → 00110101 Ans.  (ii) S → 0B → 00BB → 00B1S → 00B10B → 00B101 → 001S101 → 0011A 10 → 00110101 Ans.  (iii)      S 1   /    \ 0      B 2      /   |    \    0   B 3     B 6        /  \     |   \      1     4 S   1   S 7           /  \       |   \         1    5 A     0   B 8                |    ...