Select all the statements below which are true: Let G be a right-linear grammar.

Question

Select all the statements below which are true: Let G be a right-linear grammar. Then L(G) is accepted by some nfa. Any regular expression denotes a regular language. Any regular language can be described using a regular expression. Two regular expressions r_1 and r_2 are equivalent if they have the same number of symbols. Any finite language is a regular language. Pumping Lemma is used to show that a language is not regular. In a GTG, the edges are labeled using grammar productions. phi is a regular expression denoting {lambda} Regular languages can be described using dfa's, nfa's, regular grammars, and regular expressions. Let G be a linear grammar. Then G is a regular grammar. There are unlimited regular expressions for a given language.

Explanation / Answer

pumping lemma is used to show that a language is not regular-- True
Proof:
Assume that L is regular.
If it is regular, then the pumping lemma says that there exists some number n which is the pumping length.
Pick a specific word w belongs to L of length larger than n. The difficult part is to know which word to take.
Consider ALL the ways to partition ww into 3 parts, w=xyzw=xyz, with |xy|n|xy|n and yy non empty. For each of these ways, show that it cannot be pumped: there always exists some i0i0 such that xy^iz belongs to L.
Conclude: the word ww cannot be "pumped" (no matter how we split it to xyzxyz) in contradiction to the pumping lemma, i.e., our assumption (step 1) is wrong: L is not regular.

regular langage can be described using dfa's nfa's regular expressions and language?   Yes
Explanation:
deterministic finite automaton (DFA),
nondeterministic finite automaton (NFA),
regular expression (regexp of formal languages) or
regular grammar
The above all are used to describe Regular Language.

Any finite language is a regular language. -- yes
One-line proof: A finite language can be accepted by a finite machine.
Detailed construction: Suppose the language LL consists of strings a1,a2,…,ana1,a2,…,an.
Consider the following NFA to accept LL: It has a start state SS and an accepting state AA. In between SS and AA there are nn different paths of states, one for each aiai. The machine can only get from the beginning of the i'th path to the end if it sees exactly the string aiai.
There are -transitions from SS to the beginning of each path, and from the end of each path to AA.
For example, suppose LL consists of exactly the three stings fish, dog, and carrot. Then the NFA looks like this:

.-------- f - i - s - h --.
/
S---- d - o - g --------------A
/
'- c - a - r - r - o - t -`

two regular expressions r1 and r2 are equivalence if you have same number of symbols

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.