Language Associated with Regular Expression | Regular Expression Language Examples | 064
Playlist for all videos on this topic: • Theory of Computation or Automata Theory ...
DFA for the given regular expressions, regular expressions : L(((aa*)b)), Given that a language LA=L1∪ L2, where L1 and L2 are two other languages. If LA is known to be a regular language, then which of the following statements is necessarily TRUE?
If L1 is regular then L2 will also be regular
If L1 is regular and finite then L2 will be regular
If L1 is regular and finite then L2 will also be regular and finite
None of these
A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?
1) L is necessarily a regular language.
2) L is necessarily a context-free language, but not necessarily a regular language.
3) L is necessarily a non-regular language.
4) None of the above
Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be Σ. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack.
Which of the following statements is TRUE?
Ex. 1: Find the shortest string that is not in the language represented by the regular expression a*(ab)*b*.
Solution: It can easily be seen that , a, b, which are strings in the language with length 1 or less. Of the strings wiht length 2 aa, bb and ab are in the language. However, ba is not in it. Thus the answer is ba.
Ex. 2: For the two regular expressions given below,
(a) find a string corresponding to r2 but not to r1 and
(b) find a string corresponding to both r1 and r2.
r1 = a* + b* r2 = ab* + ba* + b*a + (a*b)*
Solution: (a) Any string consisting of only a's or only b's and the empty string are in r1. So we need to find strings of r2 which contain at least one a and at least one b. For example ab and ba are such strings.
(b) A string corresponding to r1 consists of only a's or only b's or the empty string. The only strings corresponding to r2 which consist of only a's or b's are a, b and the strings consiting of only b's (from (a*b)*).
)*(a + ) is a regular expression for L.