# Theory of Computation: Question Set – 17

#### What is a backreference in a regular expression?

A backreference is a way to refer back to a matched group in a regular expression. You can use parentheses () to create a group, and then refer to that group later in the expression using \1, \2, etc. For example, the expression (foo)bar\1 matches the string foobarfoo.

#### How do you match the beginning or end of a line in a regular expression?

You can use the caret (^) to match the beginning of a line, and the dollar sign ($) to match the end of a line. For example, the expression ^hello matches any line that starts with the word “hello”, and the expression world$ matches any line that ends with the word “world”.

#### What is the difference between a positive and negative lookahead in a regular expression?

A positive lookahead (?=) matches a pattern only if it is followed by another pattern, without including the following pattern in the match. A negative lookahead (?!), on the other hand, matches a pattern only if it is not followed by another pattern.

#### Can regular expressions be used to replace text in a string?

Yes, regular expressions can be used to replace text in a string using the replace() function. You can use the search() function to find a pattern in a string, and then replace it with a new string using the replace() function.

#### What is the difference between the dot (.) and the caret (^) in a regular expression?

The dot (.) matches any single character, while the caret (^) matches the beginning of a line. They have different meanings and are used in different contexts.

#### How do you make a regular expression case-insensitive?

You can make a regular expression case-insensitive by using the flag /i at the end of the expression. For example, the expression /hello/i matches any string that contains the word “hello”, regardless of case.

#### What is a context-free grammar?

A context-free grammar is a set of rules for generating a language, where each rule consists of a nonterminal symbol and a string of one or more nonterminal and/or terminal symbols. The nonterminal symbols represent syntactic categories, and the terminal symbols represent the actual words or symbols of the language.

#### What is a production rule in a context-free grammar?

A production rule is a rule that specifies how a nonterminal symbol can be replaced by a string of other symbols, either terminal or nonterminal. Production rules are used to generate the language defined by the grammar.

#### What is the start symbol in a context-free grammar?

The start symbol is the initial nonterminal symbol from which the language defined by the grammar can be generated. All strings generated by the grammar must be derived from the start symbol.

#### What is a parse tree in the context of context-free grammars?

A parse tree is a graphical representation of the way in which a given string in the language defined by a context-free grammar can be generated. Each node in the tree represents a nonterminal symbol, and the children of the node represent the symbols that the nonterminal can be expanded into.