Question

2. Properties of the following: (a) Regular languages (b) Context-free languages (c) Regular expressions (d) Non-deterministic finite automaton (e) Turing-recognizable and Turing-decidable languages (f) A <m B and what we can then determine (g) A <p B and what we can then determine (h) NP-hard and NP-complete.

Answer 1

(a) Regular Languages:

• It is the language of a regular expression.
• It is the language accepted by a nondeterministic finite automaton (NFA).
• It is the language accepted by a deterministic finite automaton (DFA).
• It can be generated by a regular grammar.
• It is the language accepted by an alternating finite automaton
• It can be generated by a prefix grammar
• It can be accepted by a read-only Turing machine
• It can be defined in monadic second-order logic (Büchi–Elgot–Trakhtenbrot theorem)
• It is recognized by some finite monoid M, meaning it is the preimage { w∈Σ^* | f(w)∈S } of a subset S of a finite monoid M under a monoid homomorphism f: Σ^* → M from the free monoid on its alphabet^.
• The number of equivalence classes of its syntactic congruence is finite.^{[note 8][note 9]} (This number equals the number of states of the minimal deterministic finite automaton accepting L.)
• the set-theoretic Boolean operations: union K ∪ L, intersection K ∩ L, and complement L, hence also relative complement K - L.
• the regular operations: K ∪ L, concatenation K ∘ L, and Kleene star L^*.
• the trio operations: string homomorphism, inverse string homomorphism, and intersection with regular languages. As a consequence they are closed under arbitrary finite-state transductions, like quotient K / L with a regular language. Even more, regular languages are closed under quotients with arbitrary languages: If L is regular then L / K is regular for any K.
• the reverse (or mirror image) L^R. Given a nondeterministic finite automaton to recognize L, an automaton for L^R can be obtained by reversing all transitions and interchanging starting and finishing states. This may result in multiple starting states; ε-transitions can be used to join them.

(b) Context-free languages

• Union : If L1 and If L2 are two context free languages, their union L1 ∪ L2 will also be context free. For example,
  L1 = { aⁿbⁿc^m | m >= 0 and n >= 0 } and L2 = { aⁿb^mc^m | n >= 0 and m >= 0 }
  L3 = L1 ∪ L2 = { aⁿbⁿc^m ∪ aⁿb^mc^m | n >= 0, m >= 0 } is also context free.
  L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their union says either of two conditions to be true. So it is also context free language.Note: So CFL are closed under Union.

• Concatenation : If L1 and If L2 are two context free languages, their concatenation L1.L2 will also be context free. For example,
  L1 = { aⁿbⁿ | n >= 0 } and L2 = { c^md^m | m >= 0 }
  L3 = L1.L2 = { aⁿbⁿc^md^m | m >= 0 and n >= 0} is also context free.
  L1 says number of a’s should be equal to number of b’s and L2 says number of c’s should be equal to number of d’s. Their concatenation says first number of a’s should be equal to number of b’s, then number of c’s should be equal to number of d’s. So, we can create a PDA which will first push for a’s, pop for b’s, push for c’s then pop for d’s. So it can be accepted by pushdown automata, hence context free.

  Note: So CFL are closed under Concatenation.

• Kleene Closure : If L1 is context free, its Kleene closure L1* will also be context free. For example,
  L1 = { aⁿbⁿ | n >= 0 }
  L1* = { aⁿbⁿ | n >= 0 }* is also context free.

  Note :So CFL are closed under Kleen Closure.

• Intersection and complementation : If L1 and If L2 are two context free languages, their intersection L1 ∩ L2 need not be context free. For example,
  L1 = { aⁿbⁿc^m | n >= 0 and m >= 0 } and L2 = (a^mbⁿcⁿ | n >= 0 and m >= 0 }
  L3 = L1 ∩ L2 = { aⁿbⁿcⁿ | n >= 0 } need not be context free.
  L1 says number of a’s should be equal to number of b’s and L2 says number of b’s should be equal to number of c’s. Their intersection says both conditions need to be true, but push down automata can compare only two. So it cannot be accepted by pushdown automata, hence not context free.
  Similarly, complementation of context free language L1 which is ∑* – L1, need not be context free.

  Note : So CFL are not closed under Intersection and Complementation.

• Deterministic Context-free Languages
  Deterministic CFL are subset of CFL which can be recognized by Deterministic PDA. Deterministic PDA has only one move from a given state and input symbol, i.e., it do not have choice. For a language to be DCFL it should be clear when to PUSh or POP.

  For example, L1= { aⁿbⁿc^m | m >= 0 and n >= 0} is a DCFL because for a’s, we can push on stack and for b’s we can pop. It can be recognized by Deterministic PDA. On the other hand, L3 = { aⁿbⁿc^m ∪ aⁿb^mc^m | n >= 0, m >= 0 } cannot be recognized by DPDA because either number of a’s and b’s can be equal or either number of b’s and c’s can be equal. So, it can only be implemented by NPDA. Thus, it is CFL but not DCFL.
  Note : DCFL are closed only under complementation and Inverse Homomorphism.

(c) Regular Expressions

• Union: If R1 and R2 are regular expressions, then R1 | R2 (also written as R1 U R2 or R1 + R2) is also a regular expression.

  L(R1|R2) = L(R1) U L(R2).

• Concatenation: If R1 and R2 are regular expressions, then R1R2 (also written as R1.R2) is also a regular expression.

  L(R1R2) = L(R1) concatenated with L(R2).

• Kleene closure: If R1 is a regular expression, then R1* (the Kleene closure of R1) is also a regular expression.

  L(R1*) = epsilon U L(R1) U L(R1R1) U L(R1R1R1) U ...

(d) Non-deterministic finite automaton

• The machine starts in the specified initial state and reads in a string of symbols from its alphabet. The automaton uses the state transition function Δ to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in".^[8] If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.

• The set of all strings accepted by an NFA is the language the NFA accepts. This language is a regular language. For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language. Therefore, it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the powerset construction, which may lead to an exponential rise in the number of necessary states. For a formal proof of the powerset construction.