Theory Of Computation | Subject Wise

Given
s=acbc
head(s) = First character of the string of the string
tail(s)    = All Except first character of the string
concat(head(s),head(tail(tail(s))))
concat(head(s),head(tail(tail(acbc))))
concat(head(s),head(tail(cbc)))
concat(head(s),head(bc))
concat(head(s),b)
concat(a,b)
ab

option(A)=False
A={aⁿbⁿ ∣ n = 1,2,3,…}  it is deterministic context free language(DCFL) not regular because it generates  number of a's equal to number of  b's. example: { ab, aabb, aaabbb, , , ,  aⁿbⁿ  }

option(B) = False
Equal number of a's and Equal number of b's is also Deterministic Context Free Language(DCFL) but not regular Language.

option(C) = False
L(A^∗B) ∩ B gives the set B not set A
L(A*B)= L( { B + AB + AAB + AAAB + ......B} ) // B always there in A*B
L(A*B) ∩ B = B

CFL are closed under union, concatenation(product) and kleene closure but not closed under intersection and complementation

Small correction in the diagram
Increments a given bit pattern by 1.

Table analysis for the above diagram

In CNF to derive a string of terminals of length x, Number of productions in derivation is 2x - 1
In GNF to derive a string of terminals of length x, Number of productions in derivation is x 

C is a useless symbol in S → ABCc and it cannot derive any terminal so remove it
S→ABc // now removed
Let see remaining productions
Bb → bb ( i.e. B→b)
Ab→ab (i.e.A→a)
Aa→aa (i.e. A→a)
∴S→ABc→abc

According to Chomsky Hierarchy
S1 is True = Context Sensitive Languages are the subset of recursive languages
S2 is True = Recursive languages are the superset of Context Sensitive Languages and it is not necessary that every Recursive language is Context Sensitive Languages.

(A) There is unique minimal DFA for every regular language - TRUE

(B) Every NFA can be converted to an equivalent PDA. TRUE
Every Regular Language is CFL, so we can draw PDA for regular language also.

(C) Complement of every context-free language is recursive. TRUE
CFL is a proper subset of recursive languages and recursive languages are closed under complement.

(D) = FALSE
Non-deterministic PDA is more powerful then Deterministic PDA. So, DPDA cannot handle languages/grammars with ambiguity but NDPDA can handle ambiguity languages/grammar  and DPDA is a proper subset of NDPA. so every DPDA can be converted to an equivalent NPDA(but reverse is not possible)

L(L + D)* is valid identifier because it start with only letter(L) and it followed by (L + D)* means any number of letters or digits

Recursively enumerable languages are closed under Intersection
Recursively enumerable languages are not closed under complement
Set difference= L−P can be written as L ∩ P^C. where P^C is complement of P so Set difference of these two language is not closed.

In the given regular expression r=(aa)^∗(bb)^∗b contains Kleene star(*)  where * means 0 or more occurrences
(aa)^∗(bb)^∗b = {b, , , ,, }
So, string "b" must accepted by r=(aa)∗(bb)∗b

So we can strike of option(A),option(B),option(C)

In linear grammar in which all non-terminals should be only in left side (Left linear) or right side (Right linear)
→In left-linear or left regular grammars, in which all non-terminals in right hand sides are at the left ends.
→In right-linear or right regular grammars, in which all non-terminals in right hand sides are at the right ends.
S→aSb  the non terminal S appears in middle. so It is not linear grammar

Context free grammar (CFG) are with each productions follows production rules A → B, where A single non-terminal and B is the set of terminal and non-terminal.
In CFG non terminal can appear (in left, right or in between of RHS).

The language generated by the following grammar is L={b,bb,bbb, abb, abbbbb, ababbbb} = { a^mbⁿ ∣ n>m, m≥0 }
Which is Equal to option(D)

Given
L1 be regular language(RL)
L2 be a deterministic context free language (DCFL)
L3 a recursively enumerable language(REL) but not Recursive

option(A) = True
L1∩L2 = RL ∩ DCFL = DCFL which is CFL

option(B) = False
L3∩L1 = REL ∩ Regular = REL but may or may not RECURSIVE

option(C) = True
L1∪L2 = RL ∪ DCFL= DCFL which is CFL

option(D) = True
L1∩L2∩L3 = RL ∩ DCFL ∩ REL = Recursively enumerable language(REL)

L = {a^p | p is a prime}.
String generated by this language are L= { aaa,aaaaa,aaaaaaa,aaaaaaaaaaa,......},
and in L there is no definite pattern between the string .So this language is not regular language. and also not Context Free Language.
But this language is accepted by Turing machine using trial division algorithm

Without rewinding capability and unidirectional tape movement.

• Rewind is a procedure in which  1^st element of input go to last element on tape and process it and come back to starting of input tape.
• This is done by only Turing machine(TM's) because Turing machine can move in both direction so TM's is also called bidirectional.
• In Finite State Machine input move from left to right and one by one but It cannot be rewind. So FSM can be called as unidirectional tape movement

L={w = (0 + 1)* | w has even number of 1's }
L Generating L is the set of all bit strings with even number of 1's.

Option(A) : False
This is not accepting string 110 (string 110 contains even number of 1's still not accepting)

Option(C) : False
This will accept some string which will not contain even number of 1's. example - 010, 1

Option (D) : False
This is not accepting string 11101 (String 11101 contains even number of 1's still not accepting)

Statement I - True
G is ambiguous because string ab has multiple derivation trees like
S → SS → abS → ab
S → ab.
Example 2 : string ababab has multiple derivation trees like
S → SS → abS → abSS → ababS → ababab
S → SS → SSS → abSS → ababS → ababab

Statement II - False
G does not produce all strings with equal no. of a's and b's example : string ‘aabb’ cannot be generated by G

Statement III - True
The given grammar G generates the language (ab+ba)^∗  which is Regular Language and therefore it is also DCFL

If a language L and its complement L' are both recursively enumerable then both languages are recursive. if L is recursive, then L' is also recursive and consequently both recursively enumerable

The language generated by the grammar is L= { a,b,aba,aaa,bbb,bab,aabaa, ......... }
All this strings in the language L are odd length palindromes

Given grammar is regular grammer(Type3) so it belongs to Type 0,Type 1,Type 2 as well. In the questions they are asking about highest type number

→Recursive languages are Turing Decidable
→Recursively Enumerable languages are also called as (Recognizable, partially decidable, semi-decidable , Turing-acceptable or Turing-recognizable)
Note :
→Recursive languages are also called decidable.
→a Turing machine that halts for every given input

S→aS
S→abA
S→abcA
S→abcd
option(d) is correct answer

→ Initially "q2" is final state
→ From the diagram, q0 state is connected to q1 state and q1 state is connected to q2 state through epsilon transitions.
→ In additions to q2 state, q0 and q1 states are also the final states of the DFA.

→ Generally, Finite State Machine consists of 2^x states for a given input x
→ A word is of "n bits" and we have "m" such words. So, Total number of bits = m*n.
→Total number of sates required by FSM are 2^m*n

1. s → (s)
2. s → (ss)
3. s → (s(s))
4. s → (s())
5. s → ((s)())
6. s → ((ss)())
7. s → (((s)s)())
8. s → ((()s)())
9. s → ((()(s))())
10. s → ((()())())

In General If number of 0's is divisible by 'm' and number of 1's is divisible by 'n'
then number of states = m*n

In the question Number 0's is divisible by 2 and Number of 1's is divisible by 5
So Total number of states = 2*5=10 states

Given DFA accepts all strings that ending with “01” . So the language should be (0+1)*01.
so only option(A) is correct

Method 2 :

Option(A): True
Ending with "01" {01,001,101,0001,0101,1001,1101,...} It accepts all strings.

Option(B): False
Ending with "1". {1,01,11,001,...}. The strings "1", "11" are not accepted by Finite automata.

Option(C): False
Starting and ending with "1". {11,101,111,...}. The string "11" is not accepted by Finite automata.

Option(D): False
The string "0"  is not accepted by Finite automata.

Only 2 strings are possible with 2nd, 3rd, 6th and 7th bits are 1.They are
1) 01110110
2) 01110111

option(A) : True
length of every string produced by this grammar is even
Example : abba

option(B) : True
String produced by this grammar has a maximum of 2 consecutive a’s.

option(C) : True

option(D) : False
string produced by this grammar has 4 consecutive b’s
Example : abbbbaabba
S → AB
S → aB
S → abbA
S → abbBaB
S → abbbbAabbA
S → abbbbaabba

Halting of Turing machine is an undecidable problem. There are several possible out come of Turing machine are.

1. It may halt and accept the input
2. It may halt and reject the input
3. It may never halt

Turing machine never halt by  changing the input.

• Having same number of edges and same number of states doesn’t mean that finite state machines are equivalent.
• Two finite state machines are said to be equivalent if they have the same input and output alphabets and if, starting from their respective initial states, they produce the same output for any input string.

option(A) = False
it not accepting string "aaa"

option(B) = False
it not accepting string "bbb"

option(C) = False
it not accepting string "aabb"

option(D) = True
The language accepted by given finite automata is
L = {ab, ba, aaab, ababab, bababa, ..............}
∴L is the language containing odd number of a’s and odd number of b’s.

→In General PDA has only 1 auxiliary memory.
→PDA behaves like a Turing machine when the number of auxiliary memory is 2 or more.

→Turing Machine recognizes ALL languages
→Linear Bounded Automata = CSL , CFL , RL
→Push down automata = CFL , RL
→Finite Automata recognizes Regular Language(RL) only

→ A grammar is said to be ambiguous if we can generate more than one parse for same given string.
→ Both G1 and G2 are ambiguous As both grammars have 2 derivations for same given string:
→ To generate string ababa using G1 grammar has 2 different parse trees possible
G1 : S → SbS | a

1)
S → SbS
S →SbSbS
S →ababa

2)
S → SbS
S →SbSbS
S →ababa

→ To generate string aababbb using G2 grammar has 2 different parse trees possible
G2 : S → aB | ab, A→AB | a,  B → ABb | b

1)
S → aB
S →aABb
S →aABBb
S →aABABbb
S →aababbb

2)
S → aB
S → aABb
S → aAABbb
S → aABABbb
S → aababbb

FA = Regular Language = Regular Grammar
PDA = CFL = CFG
LBA = CSL = CSG
TM = REL = REG

So, Context sensitive language can be recognized by a  LBA

0 0 1 1 2 2 = Accepted
0 0 0 1 1 1 2 2 2 2  = Not accepted
→Given Grammar is number of 0’s followed by equal number of 1’s and then followed by equal number of 2’s.
→ This grammar is accepted by linear bound automata  By using LBA which can move backward and upward and check the number of 0’s ,1's and 2's.
→This grammar is Context Sensitive language.

Statement 1 = True
It is "Equivalence problem" for the Recursive Enumerable languages and It is Undecidable. So, No Algorithm Exist.

Statement 2 = True
It is  "Halting problem of TM". It is Undecidable and So, No Algorithm Exist.

you can eliminate option(B) and option(C) and option(A)
In option(A) not accepting "ba"
In option(B) not accepting "ba"
In option(C) three is no "a"
option(D) is correct all strings we can generate

Given key is option(C)
It may be typo in question
Consider this 110 all options are eliminated

for option(C) the questions should be like this
Set of all strings containing at least two 1’s = (0+1)*1(0+1)*1(0+1)*

W^a  X^b  Y^a+b
W^a  X^b  Y^b Y^a
So first compare XY and then WY for this we require 1 stack so it is context free not regular

Statement 1 : True
Statement 2 : True
Recursive language are  closed under complement
Statement 3 : False
CFLs are not closed under complement

L = { ab, aa, baa }
Let S1 = ab , S2 = aa and S3 =baa

1.  baaaba   =   baa ab a → It is not in L*
2.  aabaaaa = aa baa aa → S2 S3 S2 → It is in L*
3.  baaabaaaabaa = baa ab aa aa baa → S3 S1 S2 S2 S3 → It is in L*
4.  baaabaaa = baa ab aa a → It is not in L*

therefore, 2 strings are in L*
Correct option is (B)

→If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called decidable
→It means for a given input it will always Halt

Both L₁ and L₂ are regular languages
Contribute you explanation with diagrams and sent that image to academyera.com@gmail.com

(a|b)(a|b)
={aa,ab,ba,bb}
Note : (a | b) means Either "a" or "b"

Click this link for explanation : https://academyera.com/ugc-net-june-2018-regular-language-3

L1 = { a^n+m bⁿa^m | n,m ≥ 0}
Written as L1 = { a^m aⁿ bⁿa^m | n,m ≥ 0}
(push a′s into stack  read b′s and pop a′s , when no b′s left on input and stack still contains a's, then  keep reading a′s in input and pop a′s , when no a's left in input , and stack is empty, then accepted).
So,L1 can implemented using PDA . So  L1 is CFL

L2 = { a^n+m b^n+m a^n+m | n,m ≥ 0}
Written as L2 = { a^x b^x  a^x | x>=0}
For every "b" we can pop a's came before "b" but for "a" which came after b we have nothing to pop in stack. So L2 can't be implemented using PDA
So L2 is not CFL

The language being accepted is a⁺. 
So, The complement of the language  a⁺ is a^∗− a⁺ = { ϵ }

If Both L and L' are Recursive enumerable then L must be recursive

Option(A) is Possible 
if L is itself is NOT RE. Then L' will also not be RE.

Option(B) is Possible
Suppose there is a language such that Turing machine halts on the input. The given language is Recursive Enumerable  but not recursive and its complement is NOT RE.
RE not closed under complement

Option(C) is Not Possible
If Both L and L' are Recursive enumerable then L must be recursive

Option(D) is Possible
Recursive closed under complement if L is recursive

Recursive Language are closed under complement
Recursive Enumerable Languages are not closed under complement
So option(B) is correct Answer
L1′ is recursive and L2′ is not recursively enumerable
If L1 is Recursive, then L1' is also Recursive because it closed under complement
IF L2 is RE then L2' is not RE because not closed under complement

1. Whether a finite state automation halts on all inputs. Decidable
2. Whether a given context-free language is regular. Undecidable [ Regularity is decidable till DCFL class]
3. A Turing machine computes the products of two numbers, UNDECIDABLE, Even though we can design a TM for calculation product of 2 numbers but here it is asking whether given TM computes product of 2 numbers, so the behavior of TM unknown hence, Undecidable.

1.  This is Turing Machine Halting problem. So, it is undecidable.
2.  CFL are not closed under complement so complement of CFL may or may not be CFL  so it is undecidable.
3.  Regular languages are closed under complementation. So, it is decidable
4.  Recursive languages are closed under complementation. So, it is decidable

Option(A) = False
A language can be CFL even if it is being accepted by Non-Deterministic PDA(N-PDA)
Example :  { ww^r : w ∈ Σ* and w^r is reverse of w }
Option(B) = True
CFL are closed under Union, Concatenation and Kleen star
Option(C) and Option(D) are False
CFL are not closed under intersection and complementation

Discuss in Discussion forum : https://academyera.com/data-structures-nielit-sta-02-12-2018

(a | b)*  which is nothing but (a + b)*
Set of all strings of a’s and b’s of any length including the null string. So L = { ε, a, b, aa , ab , bb , ba,  aaa, bbbb, bababa…….}

Power(TM) > NPDA > DPDA.
NTM and DTM are having same power
NFA and DFA have same power

option(A) : True

option(B) : False
power(NPDA) > DPDA.

option(C) : False
Power(TM) > NPDA > DPDA.

option(D) : True

→Context free language(CFL) are closed under union, concatenation and Kleene closure but not closed under intersection and complement.
→L1 ∩ R is closed under CFL

Note:
Intersection of any language with Regular language is definitely closed

→ Language generated is {aaccccdb, aaaaccccccccddbb, ...........}
→ push a's and c's into stack and reading one d in input pop 4 c's at a time and while reading b pop 2 a's and when no d's left in input and stack is empty then it is accepted. For this we require 1 stack
→ you can implement using Push Down Automata  because it have 1 stack

→Given problem is equivalent to halting problem of TM
→So, it is undecidable it means we don't have any algorithm to solve this problem

→ S → aS|bS|a|b is equvalent to (a+b)(a+b)*
→ Eliminate option(A) Which is only 1 character of length 1 either "a" or "b"
→ Eliminate option(C) Which is produces only 2 characters of  length 2 like {aa,ab,bb,ba}
→ option(B) which produces strings of length which are greater then 2 also and it starts with either a or b followed by any number of a's or b's

Regular languages are closed under prefix and suffix operations

option(A) = False
A={a​ⁿ​b​ⁿ​ |n= 0,1,2,3..}  = DCFL not Regular

option(B) = False
Equal number of a's and b's which is again DCFL not regular

option(D) = False
L(A*B*) ∩ B gives the set B not set A

Every possible string over a, b generated by L(r) not by L(s) and L(t)
So, L(r) is superset among L(s) and L(t)
L(s) is propersubset of L(r) and L(s) is propersubset of L(t)
∴ L(r) ⊇ L(s) ⊇ L(t)
Given key is 1 but it should be 4

Regular sets are closed under
→Union
→Concatenation
→Kleene's closure

1. Emptiness of Recursive Language → undecidable
2. Membership problem of Recursive language → Decidable
3. L=R  → Undecidable
4. L(G) = Σ* Completeness problem or Totality problem of RL → Undecidable

• CFL are closed under union and difference with regular language.
• Where  CFL are  not closed under intersection  and complementation a
• Complement of CFL is recursive language .
• Regular Language is closed under complementation
• CFL is closed under Intersection with Regular Language

option(A) : False
Context free language are closed under union but not complementation
L1∪L2 is CFL but complement(L1∪L2) is not CFL always

option(B) : True
L1−R = L1 ∩ R' =L1 ∩ R Always True
Regular language are closed under complementation and intersection of CFG and Regular is CFG.

option(C) : False
CFL are not closed under complementation

option(D) : False
CFL are not closed under intersection

→Every DFA is a special kind of NFA. Thus if a language L is recognized by a DFA D, then since D is a special NFA, L is also recognized by an NFA also
→You can convert any NFA to DFA So NFA and DFA are both equivalent in power

→FSA cannot remember arbitrarily large amount of information because FSA has finite memory
→FSA cannot deterministically fix the midpoint because not able to find midpoint in palindrome.
→FSA has finite memory So, Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half.

option(A) : False
L1-L2 can be written as L1 ∩ L2' = CSL
Regular languages are closed under complement
CSL are closed under intersection with regular
According to Chomsky hierarchy every CFL is CSL. So L1 ∩ L2' = CLF also

option(B) : True
L1 ∩ L2 = CFL
CSL are closed under intersection with regular languages
So L1 ∩ L2 = CSL
According to Chomsky hierarchy every CFL is CSL. L1 ∩ L2 = CLF also

option(C) : False
Every CSL compliment is not always CFL
CSL is closed under compliment
CFL is not closed under complement. So, complement of CFL may or may not be a CFL.

Turing machine is a simple mathematical model of general purpose computer - TRUE
Turing machine is more powerful than finite automata - TRUE
Turing Machine can be simulated by a general purpose computer - TRUE
All options are true none of the option is wrong

→Having same number of states and same number of final states doesn't mean that they are equivalent
→Two DFA's M1 and M2 over the same alphabet are equivalent if they accept the same language
i.e. L(M1)=L(M2)

Given RE
(00+01+10)(0+1)*
Given regular Expression can generate strings with any length(Even length string or odd Length sting) but string must start with 00 or 01 or 10
So Eliminate option(B),option(D) and option(C)
option(A) : correct
String starts with 00 or 01 or 10 not with 11

Regular languages are closed under

1. Intersection (∩)
2. Union (∪)
3. Complement
4. Kleene Closure (*)

Σ* – R1 = Σ* ∩ R1’ = It is regular language because it is closed under complement

DFA : Empty string transitions are not seen in DFA.
NFA : NDFA permits empty string transitions.

So we need to Generate stings of length 4 or less : It means string upto length 4 i.e. length 0 or length 1 or length 2 or length 3 or length 4

(0+1+ε)⁴
=ε+(0+1)¹+(0+1)²+(0+1)³+(0+1)⁴
=(ε+0+1)⁴

Given
G be a CFG Grammar
W1 and W2 are 2 strings of same Length

Example :
X → Yd | dd
Y → a

W1= dd and W2=ad
∴ |W1| = |W2|
W1 needs 1 derivation X → dd
W2 needs 2 derivation X → Y → ad

Note : They clearly specified in the option some derivations may be

→ Given regular expression is set of strings with either a or zero or more occurrence of b followed by c.
→In option(A) they not specified about zero occurrence

→ P1 = Membership algorithm in CFL is Decidable
→ P2 = CFL intersection with Regular is Decidable.
→ P3 = No algorithms to check that CFG is ambiguous or not so it is Undecidable
→ P4= we can determine ε is in language or not in the language . If Start Symbol itself contain ε then we can say it belongs to language is Decidable

So only P3 is is Undecidable

→Recursively Enumerable languages are not closed under complementation.
Proof : A_tm is Recursively Enumerable but complement(A_tm) is not Recursively Enumerable

→Recursively Enumerable languages are not closed under set difference

→ ∑* means any string using the input alphabets ∑ of any length 0 or any length
→ Σ* 001 Σ* = All string containing '001' as substring

→ Given grammar is ambiguous because it can generate more than 1 parse tree for the string "ab"

Parse Tree 1 = ab

             S 
         /      \
        S        S
      / | \      |    
     a  s  b     €
        |
        €

Parse Tree 2 = ab

      S 
   /    \        
  S      S        
 /     / | \          
€     a  s  b     
         |
         €

→The strings of a language L can be effectively enumerated means a Turing machine exists for language L which will enumerate all valid strings of the language.
→ Given Language is Recursive Language
→If the string is in lexicographic order then Turing Machine will accept the string and halt in the final state. But, if the string is not lexicographic order then Turing Machine will reject the string and halt in non-final state.
→We can not construct PDA for language L. So, the given language is not context free.
→ Given L is Recursive but not necessarily Context Free

→ Recursively Enumerable(RE) also called as recognizable, partially decidable, semi-decidable, Turing-acceptable or Turing-recognizable
→ RE are not closed under complement
→ RE are closed under Union, Intersection, Concatenation, Star Closure.

Let r1=a and r2=b

(a+b)* ≈ (a*b*)* ≈ (a*+b*)* ≈ (a+b*)* ≈ (a*+b)* ≈ (b*a+a*b)*

→Single-tape Turing Machine and Multi-tape Turing machine have same expressive power.
→Non Deterministic Turing Machine and Deterministic Turing Machine are equivalent in power.

only s2 is true

option(C) is correct

→NPDA is more powerful than DPDA
    Power(NPDA) > Power(PDA)
→NFA and DFA are both are equivalent in power
→Mealy and Moore machine have equal power.

→Mealy and Moore machines are not language acceptors. They produce output based on input and/or state using actions. They are categorized under Transducers. Language acceptors are separate classification under FSM.

→ option(A) you can not generate 1101
→ option(B) you can generate 1101
→In option(c) after 11, we can't have 01 and so 1101 can not generated 1101.
→ option(D) you can generate 1101
So option(A) and option(C) are both are correct

→ The table entries in CYK algorithm is in the form of a triangular matrix.
→ If the length of the string is ‘n’ then the Total Number of Table Entry in CYK algorithm is (n(n+1))/2
→ CYK algorithm takes O(n) time to compute each entry in table so whole table takes O(n)³ time in worst case

→Deterministic Context free language are closed under complement - True
→Deterministic Context free language are not closed under union - True
→Deterministic Context free language are closed under intersection with regular set - True

→NPDA is more power full then PDA
→Deterministic Turing machine and Non-Deterministic Turing machine are equivalent in power
→NFA and DFA also have same equivalent in power

L1,L2⊂ L3⊂ L4⊂ L5⊂ L6

Click this link for Explanation : https://academyera.com/data-structures-nielit-scientist-b-2017

((01)*(10)*)* is same as (a*b*)* , where a=01 and b=10
(a*b*)* = (a+b)* which is (01+10)*.
Both (i) and (ii) have same expression

L={ x​ⁿ​ y​ⁿ​ , such that n>=1 }
when n=1, string would be "xy"
when n=2, string would be "xxyy"
when n=3, string would be "xxxyyy"

So given language is Equal number of x's followed by y's

Statement (I) : In Statement (I) we have restriction over the number of a's and b's both being equal.
Statement (II) and Statement (III) There is no restriction over the number of a's and b's . You can have any number of x and y.

All possible strings of length 2 over Σ = {a,b} = {aa,ab,ba,bb} = total 4 strings
option(B) contains all 4 strings

NFA-l or ε-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.

An epsilon transition (also epsilon move or lambda transition) allows an automaton to change its state spontaneously, i.e. without consuming an input symbol. It may appear in almost all kinds of nondeterministic automaton in formal language theory, in particular:

1. Nondeterministic Turing machine
2. Nondeterministic pushdown automaton
3. Nondeterministic finite automaton

→The complement of a DFA can be obtained by making the non-final states as final states and vice-versa.
→The language accepted by the complemented DFA L2 is the complement of the language L1.

→Concatenation refer to Dot.
→Concatenation means Two operands(or strings) are said to be joining together
Example : AB = A•B = {xy : x ∈A & y ∈B}.

Click the link for Explanation : https://academyera.com/data-structures-nielit-scientist-b-17-12-2017

Regular languages are also closed under intersection.

Arden’s Theorem
→Arden’s Theorem is  used to convert a given DFA to its Regular Expression.
→Arden’s Theorem can be used to find a regular expression for both DFA and NFA.
→Let P and Q be two regular expressions over ∑. If P does not contain a null string ∈, then R = Q + RP has a unique solution i.e. R = QP*

(0+ɛ)(1+ɛ) = { ɛ,0,1,01 }

→NFA and DFA have same computational power
→BY default All DFA are NFA. You can convert given NFA to DFA so both NFA and DFA are Equivalent in power

→For n states
→ Number of DFA’s = 2ⁿ * n^(2*n) = 2² * 2^(2*2) = 64

→Complement of (a+b)* = ∑* - (a+b)*  = ϕ  = { } means no element is present
→Power set of {Π } = {{},{Π}}
→Power set of {}= {Π}

→ Finite Automata = 0 stacks
→ Pushdown Automata is a finite automata with extra memory called stack = 1 stack

→ Check all the options
→ In option(B) : product with 0 gives results also 0
=(0+0+0)(0+1+1)
=(0+1+1) gives results as 0 or 1
=(0+0+0) gives results as 0

→ A language L for which there exists a TM, 'T', that accepts every word in L and either rejects or loops for every word that is not in L, is said to be Recursively Enumerable

→ Only difference between Recursively Enumerable and Recursive Language is

• Recursively Enumerable  may or may not Halt
• Recursive Language is always Halt

→ The Pigeonhole Principle states that if n pigeons fly into m pigeonholes and n > m then at least one hole must contain two or more pigeons.

→ Finite state automaton can assume only a finite number of states and because there are infinitely many input sequences, by the pigeonhole principle, there must be at least one state to which the automaton returns over and over again. This is an essential feature of the automaton.

option(A) : union
(r)|(s) is a regular expression representing L(r) U L(s)

option(C) : Kleene closure
(r)* is a regular expression representing (L(r))* ; ( L(r1*)=(L(r1))* )

option(D) : Concatenation
(r)(s) is regular expression representing L(r)L(s)

Click this link for Explanation : https://academyera.com/nielit-scientific-assistance-it-2017

→3 examples of strings in L(G) : (ab, ba, aab)
→3 examples of strings not in L(G) : (a, b, aa)

Given grammar starts with R → XRX | S you can't generate only a or only b or aa

→ Any non-negative odd number Represented in binary form then LSB bit must be 1
→ Any non-negative Even number Represented in binary form then LSB bit must be 0
→ In option(C)  0*1*0*1⁺ ( +  indicate must have 1 in LSB.) So, this Language won't contain any even numbers

option(A) : S→SS | a
This is ambiguous grammar because generates more then 1 parse tree for same string "aaa"
Derivation 1 :
S→SS→Sa→SSa→Saa→aaa
Derivation 2 :
S→SS→aS→aSS→aaS→aaa

option(B) : S → 0S1 | 01S | ϵ
This is ambiguous grammar because generates more then 1 parse tree for same string "01"
Derivation 1 :
S→0S1→01
Derivation 2 :
S→01S→01

option(C) : yxxyy
S → U
U → yT
yT → yxSy
yxSy → yxTy
yxTy → yxxyy

p⁺[3-5]*[xyz] = p⁺(3+4+5)*(x+y+z)
All strings must start with character p followed by 3 or 4 or 5 either 0 occurrence or more occurrence and must end with either x or y or z

I. p443y   =  Valid
Il. p6y       = Invalid because 6 cannot used we can use only among (3,4,5).
III. 3xyz   = Invalid Strings must start with p.
IV. p35z   = Valid
V. p353535x  =Valid
Vl. ppp5  = Invalid  Strings must end with x or y or z.

Given
Regular expression (0​⁺​ 1​⁺ ​ | 2​⁺​ 3​⁺​ )*
Total Possible strings of length 4 are :
0001, 0111, 0011, 0101, 0123, 2323, 2333, 2223, 2233, 2301.
Total 10 strings are possible.
With 01 = 0111, 0011, 0001, 0101
With 23 = 2333, 2233, 2223, 2323
Using both 01 and 23 = 0123, 2301

option(A) : True
Consider the string "aab" having more then 1 parse tree
Derivation 1 :
S−>aS
S−>aaSbS
S−>aaϵbS
S−>aabϵ
S−>aab
Derivation 2 :
S−>aSbS
S−>aaSbS
S−>aaϵbS
S−>aabϵ
S−>aab

option(B) : False
An Unambiguous grammars have different Left Most Derivation and Right Most Derivation

option(C) : True

option(D) : True

Regular expression (0 | ∈) 1⁺2* (3 | ∈)
Possible strings of length 4 are :
0122, 0123, 1123, 0112, 0113, 1113, 0111, 1222, 1123, 1111, 1223, 1112;
Total 12 strings are possible

Grammar Production form
α → β
In CFG Left hand side of production can have only one variable.
|α | = 1.
Their is no restriction on β

Example
S → AB
A → a
B → b

Context free languages are closed under Union and Kleene star.
Context free languages are not closed under intersection and complement

→  The terminals in the grammar are d,b and c. There is no terminal 'a' at all. so we can eliminate options B,C,D
→ option(A) is also not correct because it is generating string "bccccd"
S → bA
S → bccA
S → bccccA
S → bccccd

None of the option is correct

→Regular expression a+b denote the set { a, b}
→Either "a" or "b"

option(A) :  Power of deterministic automata is equivalent to power of non-deterministic automata. - True

option(B) : Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata. - False
-NPDA is more powerful then DPDA

option(C) : Power of deterministic Turing machine is equivalent to power of non-deterministic Turing machine. - True

option(A)
L = { ww^R ǀ wε{0,1}* } - CFL
we can find mid-point in the expression even in a non-deterministic way

option(B)
L = { a​ ⁿ​ b​ ⁿ​ ǀ n≥0 } - CFL
push a’s and then we can pop a’s for each occurrence of b.

option(C)
L = { ww ǀ wε{0,1}* }  - CSL
we can't implement using PDA
One might think to draw a non-deterministic push down automaton, but it will not help as first symbol will be at bottom of the stack and when the second W starts, we will not be able to compare it with the bottom of stack.

option(D)
L = { a​ ⁿ​ b^{​ m}​ c^{​ m}​ d^{​ n}​ ǀ n,m ≥0 } - CFL
we can implement using PDA push a's and b's on seeing one c pop one b in stack follow the same for d on seeing d pop a. finally input became empty and stack became empty then accepted

→The term Phrase Structure Grammar for more restricted grammars in the Chomsky hierarchy : context-sensitive grammars or context-free grammars.
→Phrase Structure Grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars.
→The most general one in the given options is context sensitive because it covers the context free grammars.

"b" will appear exactly once in the given grammar so strike off options A,C,D

option(B) : aa*b
starts with "a" followed by number of a's either 0 occurrence or more occurrence and ends with "b"

S → AB→ab
or
S→AB→aAb→aab
or
S→AB→aAb→aaAb→aaab
or
S→AS→AAS→AAAS  -----so on aa*b