General

Question 1

What is the closure property?

Answer 1

If two regular languages are combined using an operator, then the resulting language is also regular

Question 2

Name the closure properties

Answer 2

Union, intersect, complement, difference, reversal, Kleene, concatenation, homomorphism, inverse homomorphism

Question 3

What is the Kleene operator?

Answer 3

The set of all finite sequences of the language

Question 4

What is homomorphism?

Answer 4

A function that converts one language into another. Such as ab = 0, bbb = 1

Question 5

How does one unionize two DFA’s?

Answer 5

lump all starting states as one, and each letter added leads to a new lumped state. If one of the languages’ states is an accepting state, the lumped union state is also regular

Question 6

How does one create a complement DFA?

Answer 6

Swap all accepting states to non accepting states, as well as all non accepting states to accepting states

Question 7

How does one create the intersection of two DFA’s

Answer 7

Lump the initial states together, then each letter creates a new lumped state. This is the same as union, except a state is only accepting if both languages states are accepting.

Question 8

What is L1 - L2 equivalent to?

Answer 8

L1 intersect L2^c

Question 9

How does one create a reversed DFA, given a DFA?

Answer 9

Create a new initial state, and link it to all of the accepting states. Then, swap all of the arrows, and make the old initial state the accepting state, and the old accepting states non accepting states.

Question 10

What is a homomorphism?

Answer 10

A string homomorphism is a function which substitute each symbol in ∑
(main alphabet) by a corresponding string in T (another alphabet)

Question 11

What is a counterexample for Infinite union of finite sets is regular.

Answer 11

Sol: all sets: {01}, {0011}, {000111} … are regular but their union {01}∪{0011}∪{000111} … will be {0n​ ​1n​ ​ | n for n>0} which is not regular.

Question 12

Find a counterexample for: If A is regular and A ∪ B is regular, then B is necessarily regular.

Answer 12

Sol: A = 01 and B = 0n​ ​1n​ ​ A is regular, A ∪ B = 01 is regular, but B is not
regular

Question 13

Is this regular? L = the number of 0’s in w is 7k (for some k) and the number of 1’s in w is 5r (for some r)

Answer 13

Sol: It is regular, you can create a DFA with 35 states which captures all possible situations for the number of 0’s and 1’s (5 reminders for 5r, and 7 reminders for 7k).

Question 14

Is this regular? L=​{​w, t​he number of 0’s in​ w ​is less than the number of 1’s}

Answer 14

Sol: it is not regular and we can prove it using pumping lemma:
1. Assume n is the pumping length.
2. Let w = 0n​ ​1n​ +1,​ (note: the |w| >= n).
3. w = xyz, so that |xy| <= n and |y| >=1, with these conditions, y should be in 0 part of the string: 0r​ ​ (r>=1),
4. So if we choose k = 2, then xyyz will be 0n​ +r1​ n​ +1​, which is not in the language (because n+r >= n+1, the number of zero’s will be greater or equal to the number of ones)

Question 15

Is this regular? L={a^n b^n, where m≠n and m, n ≥ 0}

Answer 15

Sol: Not regular, we can prove using closure properties.
L1 = 01 is regular, assume L is also regular, then L1 - L should be regular (because regular languages are closed under set difference).
L1-L = 0n​ ​1n​ ​ which we know is not regular. It is a contradiction. Then L is not regular

Question 16

Is this regular? L={​ wxwR​, where w,x∈{a,b}*and w, x >0} wR​ ​ is the reverse of string w}

Answer 16

Sol: The important thing to note about this language is the length of x is greater than 0, i.e., |x| > 0. So any string that starts and ends with the same character is acceptable by language and the remaining string becomes x.

Question 17

Is this regular? Assume L = {w, where w has equal number of 0’s and 1’s}, init (L) = {set of all prefixes of every string w∈L}

Answer 17

Sol: assume w is a string with equal number of 0’s and 1’s, then all prefixes of strings like w, will be all binary strings! (there will be no constraints on the number of zeros and ones)

Question 18

Is the following string regular? www, where w is a binary string

Answer 18

Sol: it is not regular and we can prove it using pumping lemma:
1. Assume n is the pumping length.
2. Let w = 0n​ ​1n​ 0​ n​ ​1n​ 0​ n​ ​1n​ ,​ (note: the |w| >= n).
3. w = xyz, so that |xy| <= N and |y| >=1, with these conditions, y should be in first 0 part of the string: 0r​ ​ (r>=1),
4. So if we choose k = 2, then xyyz will be 0​n+r1​ n​ ​0​n​1n​ ​0​n​1n​ ​, which is not in the language. Because you cannot divide the resulting string to three strings v all identical (vvv).

Question 19

Regular? L={​ 0m​ ​1n​​ 0m​, where m,n ≥ 0}

Answer 19

Sol: it is not regular and we can prove it using pumping lemma:
1. Assume N is the pumping length.
2. Let w = 0N​ ​1​N​0N​ ,​ (note: the |w| >= N).
3. w = xyz, so that |xy| <= N and |y| >=1, with these conditions, y should be in 0 part of the string: 0r​ ​ (r>=1),
4. So if we choose k = 2, then xyyz will be 0​N+r1​ N​ 0​ N​ ,​ which is not in the language (because N+r != N, the number of zero’s in the first part is not equal to the number of zeros at the end of the string)

Question 20

Regular? L = {​ ​w, where w​ has at least as many occurrences of (10)’s as (01)’s }

Answer 20

Yes

Question 21

How does one use inductive proof to determine the correctness of a DFA?

Answer 21

1. Assume base case of epsilon is handled
2. Show that for all strings of length k, there exists one of length k+1. To do this, show that the transition(q0, w) -> all other state invariants. ie wr -> where r = all elements in the language for each state.
3. Show that the accepting states are the correct ones

Question 22

Describe Chomsky Normal Form

Answer 22

All variables either end in a single terminal, or two Variables.

Question 23

How to turn a CFG into CNF

Answer 23

First, simplify the CFG. Then you must isolate the variables from the terminals, by turning terminals into variables that lead to a single terminal. Afterwards, convert all variables in a chain of 3 or longer into 2 by lumping 2 into 1 ie ABC -> AD, D = BC

Question 24

How do you simplify a CFG

Answer 24

1. Eliminate useless symbols
2. Eliminate epsilon productions
3. Eliminate unit productions ie A -> B

Question 25

How do you remove useless symbols

Answer 25

Remove non generating symbols, then non reachable symbols.

Question 26

What are CFL’s not closed under

Answer 26

Intersect
Difference
Complement

Question 27

What are CFL’s closed under

Answer 27

Union
Concatenation
Kleene
Substitution
Homomorphism
Inverse homomorphism
Reversal

Question 28

Is the intersect of a CFL and a regular language a CFL?

Answer 28

Yes